| Die letzten 2 Beiträge |
| 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]](http://www.matheboard.de/latex2png/latex2png.php?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]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]](http://www.matheboard.de/latex2png/latex2png.php?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)
Wo die fehlenden 2 herkommen darfst du selbst ausknobeln (Ansatz: die Summe ist nicht wirklich unendlich, die einzelnen Summanden sind >= 1). |
| 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 ?? |
|
|
