Merge-Sort Verständnis < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 21:58 Fr 11.11.2011 | | Autor: | Sin777 |
| Aufgabe | Theta(n*k + n*ln(n/k))
Was ist der größte asymptotische Wert von k in Abhängigkeit von n, so dass der Algorithmus die gleiche asymptotische
Laufzeit wie MergeSort hat? (Theta-Notation) |
Habe ich die Frage richtig verstanden, dass ich hier berechnen muss, wann n*ln(n/k) >= n*k ist? Denn die Summe im Theta ist ja nichts anderes als das Maximum der einzelnen Summenglieder. Allerdings steht ja beim Mergesort in im ln kein Bruch, weshalb ich etwas unsicher bin, was ich hier denn überprüfen muss.
Danke im Voraus.
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:07 Fr 11.11.2011 | | Autor: | Sin777 |
Mal davon abgesehen: Wie soll ich denn die Ungleichung k <= log(n/k) lösen ...
|
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 12:40 So 13.11.2011 | | Autor: | Sin777 |
Kann mir diesbezüglich niemand helfen? :)
Gruß
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:22 Di 15.11.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
Hallo Sin777,
> Mal davon abgesehen: Wie soll ich denn die Ungleichung k <=
> log(n/k) lösen ...
Nach k geht das allenfalls numerisch, nach n ist das doch kein Problem:
Ich nehme an, dass [mm]\log[/mm] den 2er-Logarithmus meint.
Also [mm]2^{k}\le 2^{\log_2\left(\frac{n}{k}\right)}[/mm]
dh. [mm]k\cdot{}2^k\le n[/mm]
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:20 So 13.11.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
