Wie komme ich auf die Rekkurenzgleichung bestimmter Algorithmen?

10.11.2016, 21:39	Auf diesen Beitrag antworten »
lellll97	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:58	Auf diesen Beitrag antworten »
lelllll97	T(n)=T(an)+T((1-a)n)
11.11.2016, 07:03	Auf diesen Beitrag antworten »
eulerscheZahl	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.

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »