T(n) ist element von O(n^2) |
| 07.04.2004, 17:04 | jstillha | Auf diesen Beitrag antworten » | ||
| T(n) ist element von O(n^2) Die Frage ist nun ob T(n) Element von O(n^2) ist gruss jstillha |
||||
| 07.04.2004, 19:25 | Filewalker | Auf diesen Beitrag antworten » | ||
welche Gleichung stellt O(n^2) denn dar?? oder ist das eine von vornhinein definierte gleichung?? |
||||
| 07.04.2004, 21:34 | jstillha | Auf diesen Beitrag antworten » | ||
O(n^2) stammt aus der Algorithmenanalyse von Computerprogrammen, gennant BigO. O(n^2) heisst soviel wie: wenn ich n input habe ist meine Laufzeit des Programms n^2. |
||||
| 07.04.2004, 22:55 | Filewalker | Auf diesen Beitrag antworten » | ||
also zu der frage, ob t teilmenge von O(n)=n^2 ist würde ich sagen nein. den T(3)=9*T(1)+3=9*1+3=12 O(3)=9 demnach ist t nicht teilmenge von o, oder versteh ich da was falsch?? rekursive induktion, ohje das is ja auch schon wieder n jahr her. werd mal gucken, was ich dazu noch hinkrieg gruß luke |
||||
| 07.04.2004, 23:40 | Filewalker | Auf diesen Beitrag antworten » | ||
oh oh oh ich seh grad vollständige rekursion und höhere mathematik, da bin ich lieber direkt ruhig, bevor ich irgend nen mist rede. |
||||
| 08.04.2004, 09:58 | epikur | Auf diesen Beitrag antworten » | ||
f(n) ist Element von O(g(n)) wenn ein c > 0 und ein n0 existieren so das für alle n >= n0 f(n) < c*g(n) gilt. g ist also eine verallgemeinerte obere Schranke für f. Soviel zur Definition. Um deine Aussage zu beweisen sollten wir also ein n0 und ein c angeben und dann die geforderte Ungleichung zeigen. |
||||
| Anzeige | ||||
|
|
||||
| 12.04.2004, 01:10 | SirJective | Auf diesen Beitrag antworten » | ||
RE: T(n) ist element von O(n^2)
Da ich nicht weiß, wie die Rekursion funktionieren soll, wenn n nicht durch 3 teilbar ist, beschränke ich mich zunächst auf den Fall von Dreierpotenzen. Betrachten wir die Funktion . Es ist S(n) <= T(n). Für diese Funktion S gilt . Damit wächst T mindestens so schnell wie n^2. Na toll. Eine Abschätzung von oben wäre für die Aufgabe allerdings hilfreicher... OK, hab noch was: Versuchen wir's mit der Gleichung für Dreierpotenzen n. Die müsste mal per Induktion nachweisen können, im Induktionsschritt von n auf 3*n. Dann muss du noch wissen, wie die anderen n zu handhaben sind, da könnte z.B. eine gerundete Division gemeint sein. In dem Fall musst du z.B. nachweisen für das k mit . Dann brauchst du nur noch die obere Schranke entsprechend anpassen. Wenn wir einfach 3/2*n^2-n/2 ersetzen durch 3/2*(n+1)^2-(n+1)/2 = 3/2*n^2 + 5n/2 + 1, dann müssen wir diese Schranke durch ein reines Quadrat abschätzen. Wir können uns nun eine beliebige Zahl c aussuchen, die größer ist als 3/2, und finden dann ein n0, so dass die von Epikur angegebene Formel erfüllt ist. Für c = 3 kann man z.B. n0 = 3 wählen. Gruss, SirJective |
||||
| 14.04.2004, 10:33 | jstillha | Auf diesen Beitrag antworten » | ||
Danke für eure Hilfe Gruss jstillha |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
