Informatiker Board | Druckvorschau: Mergesort

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Praktische Informatik (http://www.informatikerboard.de/board/board.php?boardid=6)
---- Algorithmen (http://www.informatikerboard.de/board/board.php?boardid=17)
----- Mergesort (http://www.informatikerboard.de/board/thread.php?threadid=2595)

Geschrieben von Marcell99 am 20.11.2015 um 13:50:

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

Geschrieben von eulerscheZahl am 20.11.2015 um 15:43:

$[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).