Laufzeit - Master Theorem
-
Es sei T(n) = 2*T(n/2) + Theta(n), T(1)=1 und T wachsend gegeben. Per Master-Theorem kann man zeigen, dass T(n) = Theta(n*log(n)).
Folglich ist ein Fehler in folgender Überlegung. Wo ist er?
Für n=1:
T(n) = T(1) = 1 = Theta(1) = O(n)Für n > 1, n gerade:
Induktionsvoraussetzung: T(m) in O(m) für m < n, m gerade oder m = 1.
Da n/2 < n
T(n) = 2*T(n/2) + Theta(n) = 2*O(n/2) + Theta(n) = Theta(n)Per vollständige Induktion folgt, dass T(n) = Theta(n) für alle n gerade.
Da T wachsend gilt T(n) = Theta(n) für alle n.
-
Hallo,
ich glaube nicht, dass du den Beweis so mit vollständiger Induktion führen kannst.
In deinem O(foo) steckt ja ein impliziter Faktor und den übersteigst du bei wachsender Rekursionstiefe, d.h. du addierst beliebig viele O(n) aufeinander, irgendwann.
Beispiel:
O(n) + O(n) + O(n) = O(n)
aber
Summe_i=1^k (O(n)) liegt eben nicht mehr in O(n), da du k beliebig groß wählen kannst, sondern in O(k * n).EDIT Nachtrag: Was du machen müsstest: Du müsstest dir die Rekursion als Baumstruktur hinzeichnen und dann ausrechnen, welche Aufwand auf jeder Ebene des Baums entsteht. Also oben O(n), danach 2*O(n/2), bis ganz unten n*O(1). Wenn ich das richtig sehe, entsteht überall ein Aufwand O(n)?
Wenn du die addierst, müsste dann O(n*logn) rauskommen, da log n die Höhe des Baums ist (Binärteilung, Zweiteilung an jedem Knoten, eigentlich log_2, aber das ist für die Komplexität egal, weil du die Logarithmen ja mit einem konst. Faktor ineinander umwandeln kannst).
Viele Grüße
Christian
-
Genau, das Problem ist, dass Du die konstanten Faktoren vernachlässigst. Das darf man natürlich nicht prinzipiell tun, wenn man beispielsweise linear viele konstante faktoren addiert, dann ist das eben linear und nicht konstant. Ein Ansatz mit Induktion funktioniert schon, aber man muß ihn geeignet formulieren.
Hier: T(n) = c_1*n+c_2, für n<=n_0 dabei sind c_1,c_2 konstanten, die noch geeignet gewählt werdfen dürfen.
Jetzt ist für nachzurechnen:
T(n) = 2*T(n/2) + c_3*n = 2*(c_1)*n/2 + c_2 + c_3 * n = c_1*n + c_2 + c_3*n = (c_1+c_3)*n + c_2
und das sollte c_1*n+c_2 sein. Das klappt aber nur wenn c_3 <=0 ist, was aber nicht erlaubt ist. Mit dem gleichen Ansatz und T(n) = c_1* n*log n +c_2*n + c_3 sollte der Beweis aber durchgehen.
-
Ich hab das Problem gefunden.
Zu zeigen ist:
Es gibt ein c, so dass für alle n gilt f(n) < c*n.Ich habe gezeigt:
Für alle n gibt es ein c, so dass gilt f(n) < c*n.Letzteres ist eine triviale Aussage welche für jede Folge erfüllt ist.
-
Uhm.. geht das Master Theorem nicht eher so:
Man berechnet n^(log a zu Basis b), hier also dann n^1. Dann gilt f(n) e Theta(n^(log a b)), also
Theta(n) e Theta (n). Das ist wahr, also gilt für die Laufzeit
T(n) e Theta(n logn).Da wird nichts induziert oder sonstwas. Höchstens Terme umgeformt um das Theorem anwenden zu können.
e= Element von
-
Diamond schrieb:
Uhm.. geht das Master Theorem nicht eher so:
...
Darum geht's ja nicht. Er hat ja einen (vermeintlichen) Widerspruch zum Master Theorem hergestellt.
Chris
-
Ouch, gehörig verlesen
