Informatiker Board | Algorithmen

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Mergesort

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Mergesort

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Marcell99
Eroberer

Dabei seit: 14.11.2015
Beiträge: 53

Mergesort

Zitatantwort auf diesen Beitrag erstellen

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

20.11.2015 13:50

Nehmen Sie Marcell99 in Ihre Freundesliste auf

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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

__________________
Syntax Highlighting fürs Board (Link)

20.11.2015 15:43

Nehmen Sie eulerscheZahl in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Mergesort