 Wie komme ich auf die Rekkurenzgleichung bestimmter Algorithmen? |
lellll97
Grünschnabel
Dabei seit: 10.11.2016
Beiträge: 1
 |
|
| Wie komme ich auf die Rekkurenzgleichung bestimmter Algorithmen? |
     |
Meine Frage:
Ich verstehe noch nicht so ganz wie man auf die Rekurrenzgleichungen von Sortieralgorithmen kommt, gibt es da irgendwelche Ansätze, die mir bei der Überlegung weiterhelfen?
Meine Ideen:
Eine Beispielaufgabe wäre: Angenommen Quicksort wählt das Pivotelement in jeden Schritt so, dass die Folge im Verhältnis 0<a<1/2 in zwei Folgen aufgeteilt wird. Zeigen Sie, dass in diesem Fall die Laufzeit von Quicksort aus O(n*log(n)) ist.
Ja, diese Aufgabe wurde auch schonmal in einem MatheForum gestellt und auch beantwortet allerdings fehlt mir da der entscheidende Schritt und zwar wie ich von dieser Formulierung auf die Rekurrenzgleichung von
T(n)=T(?n)+T((1??)n) komme. Kann das leider kaum nachvollziehen...
|
|
10.11.2016 21:39 |
|
|
lelllll97
unregistriert
|
|
|
|
10.11.2016 21:58 |
|
|
|
|
Du hast n Zahlen, die du sortieren willst. Wenn du die mit Verhältnis a aufteilst, hast du einen Teil mit ![[latex]a\cdot n[/latex]](http://www.matheboard.de/latex2png/latex2png.php?a\cdot n) Zahlen und einen mit \cdot n[/latex]](http://www.matheboard.de/latex2png/latex2png.php?(1-a)\cdot n) .
Die beiden Teilfolgen müssen noch sortiert werden:
![[latex]\underbrace{T(n)}_{\hbox{alles sortieren}} = \underbrace{\mathcal{O}(n)}_{\hbox{Zahlen in zwei Teile zerlegen}} + \underbrace{T(a\cdot n)}_{\hbox{einen Teil sortieren}} + \underbrace{T((1-a)\cdot n)}_{\hbox{anderen Teil sortieren}}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\underbrace{T(n)}_{\hbox{alles sortieren}} = \underbrace{\mathcal{O}(n)}_{\hbox{Zahlen in zwei Teile zerlegen}} + \underbrace{T(a\cdot n)}_{\hbox{einen Teil sortieren}} + \underbrace{T((1-a)\cdot n)}_{\hbox{anderen Teil sortieren}})
Beachte, dass die Zahlen in zwei Mengen aufgeteilt werden müssen: die, die kleiner als das Pivot sind und die größeren.
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
11.11.2016 07:03 |
|
|
|
