Lösung der Wiederholungsbeziehung $ t (n) = 2T ( lfloor n/2 rfloor) + n $

Question

Lösen der Rezidivbeziehung $ t (n) = 2T ( lfloor n/2 rfloor) + n $.
Das Buch, aus dem dieses Beispiel stammt, behauptet fälschlicherweise, dass $ t (n) = o (n) $ durch Erraten von $ t (n) leq cn $ und dann argumentieren

$ qquad begin {align*} t (n) & leq 2 (c lfloor n/2 rfloor) + n & leq cn + n & = o (n) quad quad quad longleftarrow text {falsch !!} end {align*} $

Da $ C $ konstant ist. Der Fehler ist, dass wir das nicht bewiesen haben genau Form der induktiven Hypothese.

Oben habe ich genau zitiert, was das Buch sagt. Jetzt ist meine Frage, warum wir nicht $ cn+n = dn $ schreiben können, wobei $ d = c+1 $ und jetzt haben wir $ t (n) leq dn $ und daher $ t (n) = o (n) $?

Notiz:

1. Die richtige Antwort lautet $ t (n) = o (n log n). $.
2. Das Buch, das ich hier beziehe, ist Einführung in Algorithmen von Cormen et al., Seite 86, 3. Auflage.

Answer 1

Die Autoren geben die Antwort:

Der Fehler ist, dass wir das nicht bewiesen haben genaue Form der induktiven Hypothese, dh $ t (n) Leq Cn $.

Zugegeben, das ist schwer zu verstehen, ob Sie nicht für Induktionen (rechts) verwendet werden, da sie die Induktion nicht explizit/streng ausführen. Kurz gesagt: Sie müssen haben eines Konstant $ C $ für alle $ n $, aber dieser (UN) Proof baut viele (eine pro $ n $).

---

Denken Sie langen daran, was $ t (n) in o (n) $ bedeutet:

$ qquad displayStyle existiert c in mathbb {n}. , existiert n_0 in mathbb {n}. , forall n geq n_0. , t (n) leq cn $

oder gleichwertig,

$ qquad displayStyle existiert c in mathbb {n}. , forall n in mathbb {n} t (n) leq cn $.

Die zweite Form funktioniert besser für eine Induktion, da Sie den Anker kennen. Also brauchst du eines konstante $ c $, die eine Obergrenze für alle $ n $.

Lassen Sie uns untersuchen, was die Induktion tut:

• Induktionsanker: Der Anker von $ t $ wird nicht ausdrücklich angegeben, aber er ist konstant, also finden wir ein geeignetes $ c $.
• Induktionshypothese: Es gibt einige $ c $, so dass $ t (k) leq cn $ für alle $ k leq n $ für einige willkürliche, aber festgelegte $ n $ ist.
• Induktiver Schritt: Konstruieren Sie wie in der Frage $ D> C $ so, dass $ t (n+1) leq dn $.

In der Tat konstruieren wir a Neu Konstant für jeden $ n $. Das passt überhaupt nicht zur Definition von $ o $! Und schlimmer noch, es ist völlig bedeutungslos: jeder Funktion kann durch "begrenzt" durch Jeder andere Funktionieren Sie, wenn Sie den Faktor mit $ n $ anpassen können.

In Bezug auf den Induktionsbeweis muss $ C $ Teil des Anspruchs sein (und es ist im $ o $ versteckt), der außerhalb der Einführung "außerhalb" gebunden ist. Dann taucht das gleiche $ c $ in Anker, Hypothese und Schritt auf. Siehe den letzten Teil von Diese Antwort zum Beispiel.