Mergesort

Neue Frage »

Auf diesen Beitrag antworten »
Marcell99 Mergesort

Meine Frage:
Der benötigte Speicherplatz S(n) für den Sortieralgorithmus Mergesort zum Sortieren
von n = 2^k, k ? N, Zahlen ist gegeben durch S(n) = n + n/2 + S( n/2) , S(1) = 1.
Zeigen Sie, dass gilt S(n)=3n-2

Meine Ideen:
ich weiß was der moergesort ist aber ich weiß nicht wie ich diese Aufgabe machen kann.
oder wie ich das zeigen kann ??
kann mir vielleicht jemand die Aufgabe erklären ??
 
Auf diesen Beitrag antworten »
eulerscheZahl

[latex]S(n) = n + \frac{n}{2} + S\left(\frac{n}{2}\right) = n + \frac{n}{2}+ \frac{n}{2}+ \frac{n}{4} + S\left(\frac{n}{4}\right) = n + \frac{n}{2}+ \frac{n}{2}+ \frac{n}{4} + \frac{n}{4} + \frac{n}{8} + S\left(\frac{n}{8}\right) = \dots[/latex]
[latex]S(n) = n + 2\cdot \sum\limits_{i=1}^{\infty}\frac{n}{2^i} = n + 2n\cdot \sum\limits_{i=1}^{\infty}\frac{1}{2^i} = 3n[/latex]
Wo die fehlenden 2 herkommen darfst du selbst ausknobeln (Ansatz: die Summe ist nicht wirklich unendlich, die einzelnen Summanden sind >= 1).
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »