Komplexitätbeweis Algorithmus < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Es ist z.z., dass de Algorithmus T für N = [mm] 2^{n} [/mm] Laufzeit O(N log(N)) hat. Entsprechend sei T(N) die Laufzeit des Algorithmus. Es gilt, dass es eine Konstante c gibt, so dass T(N) [mm] \le [/mm] cN + 2T(N/2) und T(1) = 0. |
Sei N = [mm] 2^n [/mm] eine Zweierpotenz.
Induktion über n:
n = 0: klar!
n->n+1:
[mm] T(2^{n+1}) [/mm]
[mm] \le [/mm] c [mm] 2^{n+1} [/mm] + 2 [mm] T(2^{n})
[/mm]
[mm] \le [/mm] c [mm] 2^{n+1} [/mm] + 2 (c [mm] 2^{n} log(2^{n}))
[/mm]
= c [mm] 2^{n+1} [/mm] (1 + [mm] log(2^{n}))
[/mm]
...
= c [mm] 2^{n+1} log(2^{n+1})
[/mm]
Entsprechend lautet meine Frage nun wie ich die ... korrekt ausfülle, d.h. wie aus der vorletzten Zeile die letzte folgt??
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:20 So 23.11.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
