Rekursionsgleichung < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:57 Do 18.09.2008 | | Autor: | tommy987 |
| Aufgabe | Zu lösen ist folgende Rekursionsgleichung:
T(n) = [mm] O(n^{2}) [/mm] + [mm] 2*T(\bruch{n}{2}) [/mm] mit T(1) = O(1) |
Ich komme hier auf keine allgemeine Gleichung und kann diese dann natürlich auch nicht lösen.
Bei meiner Lösung kommt folgendes raus:
T(n) = [mm] O(n^{2}) [/mm] + [mm] 2*O((\bruch{n}{2})^{2}) [/mm] + [mm] 4*O((\bruch{n}{8})^{2}) [/mm] + [mm] 8*T(\bruch{n}{16})
[/mm]
Aus dieser Gleichung komm ich auf keine allg. Gleichung.
Vielleicht kann mir wer helfen?
lg
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:18 Do 18.09.2008 | | Autor: | bazzzty |
Hallo,
Du solltest vielleicht noch sagen, wie ihr die Aufgaben lösen sollt. Wenn Dir das Master's Theorem was sagt - damit geht es sehr einfach...
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 08:59 Fr 19.09.2008 | | Autor: | tommy987 |
Wir müssen diese Aufgabe ohne Master-Methode lösen.
Das Ergebnis soll die obere Schranke der Laufzeit sein, ausgerechnet und nicht geschätzt.
In diesem Fall wäre die Anwort [mm] O(n^{2}) [/mm] laut Prof.
Nur wie komme ich rechnerisch ohne Master-Theorem auf diese Anwort?
lg
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:01 Fr 19.09.2008 | | Autor: | M.Rex |
Hallo
Sehe ich das richtig, dass
[mm] T(n)=\underbrace{O(n^{2})}_{n=1}+\underbrace{\blue{2}\cdot{}O((\bruch{n}{\green{2}})^{2})}_{\red{n=2}}+\underbrace{\blue{4}\cdot{}O((\bruch{n}{\green{8}})^{2})}_{\red{n=3}}+\underbrace{\blue{8}\cdot{}T(\bruch{n}{\green{16}})^{2}}_{\red{n=4}}+...
[/mm]
Und du willst wissen, wie es weitergeht? Und dann am Ende eine Formel haben?
Die Roten Zahlen sind ja die Laufindizes, also musst du versuchen, die anderen farbigen Teile in Abhängigkeit von denen zu bekommen.
Betrachte mal die blauen Zahlen.
2;4;8
Es gilt: [mm] 1=2^{0}=2^{1-1}
[/mm]
[mm] 2=2^{1}=2^{2-1}
[/mm]
[mm] 4=2^{2}=2^{3-1}
[/mm]
Also kannst du die blaue Zahl im k-ten Teilsummand mit [mm] 2^{k-1} [/mm] berechnen
Für die grünen Zahlen gilt (ab n=3)
[mm] 8=2^{3}, 16=2^{4}
[/mm]
Also kannst du T(n) denke ich auch als
[mm] T(n)=O(n^{2})+2\cdot{}O((\bruch{n}{2})^{2})+\summe^{n}_{\red{i=3}}2^{i-1}\cdot{}T(\bruch{n}{2^{i}})^{2} [/mm] Schreiben.
Und jetzt kannst du evtl zeigen, dass O(n²) eine Schranke ist.
Ich weiss nicht, ob das jetzt das ist, was du suchst, also lasse ich die Frage mal auf unbeantwortet.
Marius
|
|
|
|
