Informatiker Board | Druckvorschau: Wie komme ich auf die Rekkurenzgleichung bestimmter Algorithmen?

Geschrieben von lellll97 am 10.11.2016 um 21:39:

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...

Geschrieben von eulerscheZahl am 11.11.2016 um 07:03:

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]$ Zahlen und einen mit $[latex](1-a)\cdot n[/latex]$ .
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]$
Beachte, dass die Zahlen in zwei Mengen aufgeteilt werden müssen: die, die kleiner als das Pivot sind und die größeren.