Komplexitätsangabe < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:02 Mi 09.02.2011 | | Autor: | Wimme |
Hallo!
Kann mir vielleicht jemand kurz erklären, warum
[mm] (n+1)^{3n} \cdot 3^n \in 2^{\mathcal{O}(nlogn)} [/mm]
sein soll?
Wäre sehr dankbar!
Gruß,
Wimme
PS. Wie macht man denn hier jetzt eine Vorschau?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:25 Mi 09.02.2011 | | Autor: | felixf |
Moin Wimme
> Kann mir vielleicht jemand kurz erklären, warum
> [mm](n+1)^{3n} \cdot 3^n \in 2^{\mathcal{O}(nlogn)}[/mm]
> sein soll?
>
> Wäre sehr dankbar!
Es ist $(n + [mm] 1)^{3 n} 3^n [/mm] = [mm] \exp(3 [/mm] n [mm] \log(n+1) [/mm] + n [mm] \log [/mm] 3) = [mm] 2^{3 n \log(n+1)/\log_2 + n \log 3/\log_2}$.
[/mm]
Du musst also $3 n [mm] \log(n+1)/\log_2 [/mm] + n [mm] \log 3/\log_2 [/mm] = O(n [mm] \log [/mm] n)$ nachweisen.
> PS. Wie macht man denn hier jetzt eine Vorschau?
Hast du den neuen oder alten Editor? Beim alten steht unter dem Eingabefenster ein Button "Vorschau", auf den du klicken musst.
LG Felix
|
|
|
|
