Rekursion und Landau < Funktionalanalysis < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:44 Mi 26.08.2009 | | Autor: | ZodiacXP |
| Aufgabe | Zu zeigen:
$T(n) := 2*T(⌊n/2⌋) + n [mm] \in \Omega [/mm] (n*lg(n))$
Wobei [mm] $\lfloor [/mm] n/2 [mm] \rfloor$ [/mm] der abgerundete Wert von n/2 ist.
T(n) [mm] \in [/mm] O(n*lg(n)) wurde schon gezeigt. |
Es soll die Substitution verwendet werden. Habe ich:
$T(n) [mm] \ge [/mm] 2*(c* [mm] \lfloor [/mm] n/2 [mm] \rfloor *lg(\lfloor [/mm] n/2 [mm] \rfloor) [/mm] + n$
Nun rechne ich weiter und dann hakt es:
... $ [mm] \ge c*(n-1)*lg(\lfloor [/mm] n/2 [mm] \rfloor) [/mm] + n$
Habe mir gedanken gemacht und weis was nicht geht:
$ [mm] \ge [/mm] c*(n-1)*lg(n/2) + n$
$ [mm] \ge c*(n)*lg(\lfloor [/mm] n/2 [mm] \rfloor) [/mm] + n$
Nur leider finde ich keinen Ansatz der in die richtige Richtung geht.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 04:20 Do 27.08.2009 | | Autor: | felixf |
Hallo!
> Zu zeigen:
> [mm]T(n) := 2*T(⌊n/2⌋) + n \in \Omega (n*lg(n))[/mm]
>
> Wobei [mm]\lfloor n/2 \rfloor[/mm] der abgerundete Wert von n/2
> ist.
> T(n) [mm]\in[/mm] O(n*lg(n)) wurde schon gezeigt.
> Es soll die Substitution verwendet werden. Habe ich:
>
> [mm]T(n) \ge 2*(c* \lfloor n/2 \rfloor *lg(\lfloor n/2 \rfloor) + n[/mm]
Fuer $n [mm] \ge [/mm] 3$ gilt [mm] $\floor{n/2} \ge [/mm] n/2 - 1/2 [mm] \ge \frac{n}{3}$. [/mm] Sei nun $c < [mm] \frac{1}{\log 3}$ [/mm] (man kann $c$ ja beliebig kleiner machen) und $n$ gross genug mit $n (1 - c [mm] \log [/mm] 3) [mm] \ge \frac{1}{\log 3} \log(n/3) \ge [/mm] c [mm] \log [/mm] n - c [mm] \log [/mm] 3$ (es gibt ein [mm] $n_0$ [/mm] so, dass dies fuer alle $n [mm] \ge n_0$ [/mm] erfuellt ist).
Dann gilt (fuer $n [mm] \ge \max\{ n_0, 3 \}$) [/mm] $T(n) = 2 [mm] T(\lfloor [/mm] n/2 [mm] \rfloor) [/mm] + n [mm] \ge [/mm] 2 c [mm] \lfloor [/mm] n/2 [mm] \rfloor \log \lfloor [/mm] n/2 [mm] \rfloor [/mm] + n [mm] \ge [/mm] c (n - 1) [mm] \log \frac{n}{3} [/mm] + n [mm] \ge [/mm] c n [mm] \log [/mm] n$
LG Felix
|
|
|
|
