Rekurrenzenrelationen lösen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 12:44 Do 18.11.2010 | | Autor: | pyw |
| Aufgabe | Bestimmen Sie jeweils eine möglichst kleine obere Schranke für T(n) in folgenden Rekurrenzgleichungen:
(a) [mm] T(n)=T(\frac{n}{3})+T(\frac{n}{4})+n
[/mm]
(b) [mm] T(n)=2T(n^{\frac{1}{4}})+1
[/mm]
(c) [mm] T(n)=\begin{cases} 1, & \mbox{für } n\leq a \\ T(n-a)+n+1, & \mbox{sonst } \end{cases}
[/mm]
(d) [mm] T(n)=\sqrt{n}T(\sqrt{n})+n [/mm] |
Hallo,
in meiner Übungsserie bin ich auf obige Aufgaben gestoßen. Abgabe ist morgen. Aber selbst wenn ich die Aufgaben nicht rechtzeitig löse, will ich trotzdem wissen, wies geht:
(a) habe mithilfe der Substitutionsmethode (siehe ![[]](/images/popup.gif) Wikipedia) gezeigt, dass [mm] T(n)\in O(n\ln(n)). [/mm] Dazu brauchte es aber am Anfang schon diese Vermutung. Auf Wunsch führe ich den Beweis hier auf;)
(b): Hier bin ich noch nicht durch. Vielleicht geht auch die Substitionsmethode, mit der Vermutung [mm] T(n)\in O(n^k) [/mm] für ein k ...
(c) und (d): Leider weiß ich hier überhaupt nicht, wie ich anfangen kann.
Kann mir jemand bitte insbesondere für (b) bis (d) Hinweise geben? Wäre sehr dankbar dafür!
freundliche Grüße,
pyw
PS: Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:01 Sa 20.11.2010 | | Autor: | felixf |
Moin!
> Bestimmen Sie jeweils eine möglichst kleine obere Schranke
> für T(n) in folgenden Rekurrenzgleichungen:
> (a) [mm]T(n)=T(\frac{n}{3})+T(\frac{n}{4})+n[/mm]
> (b) [mm]T(n)=2T(n^{\frac{1}{4}})+1[/mm]
$T(n) = 2 [mm] T(n^{1/4}) [/mm] + 1 = [mm] 2^2 T((n^{1/4})^{1/4}) [/mm] + 2 + 1 = [mm] 2^2 T(n^{1/4^2}) [/mm] + (2 + 1)$
Allgemein bekommt man dann $T(n) = [mm] 2^k T(n^{1/4^k}) [/mm] + [mm] (2^{k-1} [/mm] + [mm] \dots [/mm] + [mm] 2^0) [/mm] = [mm] 2^k [/mm] [ [mm] T(n^{1/4^k}) [/mm] + 1 ] - 1$ fuer $k [mm] \in \IN$.
[/mm]
Sei $n = [mm] t^{4^k}$; [/mm] dann ist [mm] $n^{1/4^k} [/mm] = t$ und $T(n) = [mm] T(t^{4^k}) [/mm] = [mm] 2^k [/mm] [ T(t) + 1 ] - 1$.
Ist also $n = [mm] t^m$, [/mm] so ist $T(n) [mm] \approx \sqrt{m} [/mm] T(t)$. Nun ist $m = [mm] \log_t [/mm] n$. Deswegen eine Vermutung: $T(n) = [mm] O(\sqrt{\log n})$.
[/mm]
> (c) [mm]T(n)=\begin{cases} 1, & \mbox{für } n\leq a \\ T(n-a)+n+1, & \mbox{sonst } \end{cases}[/mm]
Schreibe $n = q a + r$ mit $1 [mm] \le [/mm] r [mm] \le [/mm] a$.
Dann ist
$T(r) = 1$,
$T(r + a) = 2 + (r + a)$,
$T(r + 2 a) = 3 + (r + a) + (r + 2 a)$,
$T(r + 3 a) = 4 + (r + a) + (r + 2 a) + (r + 3 a)$,
oder allgemein: $T(n) = T(r + q a) = q + q r + a [mm] \sum_{i=1}^q [/mm] i = q (r + 1) + [mm] \frac{a q (q + 1)}{2} [/mm] = q [mm] \cdot \frac{2 r + 2 + a q + a}{2} [/mm] = q [mm] \cdot \frac{n + (2 + a + r)}{2} [/mm] = q n/2 + (q a)/2 + q (2 + r) [mm] \le n^2 [/mm] + n/2 + 3 n$
> (d) [mm]T(n)=\sqrt{n}T(\sqrt{n})+n[/mm]
$T(n) = [mm] n^{1/2} T(n^{1/2}) [/mm] + n$
[mm] $T(n^{1/2}) [/mm] = [mm] n^{1/4} T(n^{1/4}) [/mm] + [mm] n^{1/2}$
[/mm]
[mm] $T(n^{1/4}) [/mm] = [mm] n^{1/8} T(n^{1/8}) [/mm] + [mm] n^{1/4}$
[/mm]
[mm] $T(n^{1/8}) [/mm] = [mm] n^{1/16} T(n^{1/16}) [/mm] + [mm] n^{1/8}$
[/mm]
Also:
$T(n) = [mm] n^{1/2} (n^{1/4} T(n^{1/4}) [/mm] + [mm] n^{1/2}) [/mm] + n = [mm] n^{1/4 + 1/2} T(n^{1/4}) [/mm] + 2 n = [mm] n^{1/8 + 1/4 + 1/2} T(n^{1/8}) [/mm] + [mm] n^{1/4 + 1/4 + 1/2} [/mm] + 2 n = [mm] n^{1/16 + 1/8 + 1/4 + 1/2} T(n^{1/16}) [/mm] + [mm] n^{1/8 + 1/8 + 1/4 + 1/2} [/mm] + 3 n = [mm] n^{1 - 1/16} T(n^{1/16}) [/mm] + 4 n$
Allgemein: $T(n) = [mm] n^{1 - 1/2^k} T(n^{1/2^k}) [/mm] + k n$
Ist $n = [mm] t^{2^k}$, [/mm] so ist also $T(n) = n / t T(t) + k n [mm] \approx [/mm] n T(t) + n [mm] \log_2 \log_t [/mm] n$
Nimmt man $T(t) = O(1)$ an, waer eine Vermutung also $T(n) = O(n [mm] \log\log [/mm] n)$.
Vielleicht hilft das alles weiter...
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:06 So 21.11.2010 | | Autor: | pyw |
Hallo felixf,
vielen Dank für deine Hilfe. Ich kann mit den neuen Lösungsmethoden viel anfangen.
mfg pyw
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:20 So 21.11.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
