Die Bestimmung BIGO ein erneutes Auftreten

Question

T (1) = c    
T (n) = T (n/2) + dn

Wie würde ich BIGO dieser Bestimmung schnell?

Answer 1

Verwenden wiederholt und Rücksubstitution das Muster finden. Ein Beispiel hier .

Answer 2

Ich bin mir nicht ganz sicher, was dn, aber vorausgesetzt, Sie eine Konstante, die durch n multipliziert bedeuten:

Laut Wolfram Alpha , die Rekursionsgleichung Lösung für:

f(n) = f(n / 2) + cn

ist:

f(n) = 2c(n - 1) + c1

, die diese O(n) machen würde.

Answer 3

Nun, der Rezidiv Teil der Beziehung ist die T (n / 2) Teil, der wirksam ist, den Wert von n jedes Mal halbiert wird.

So müssen Sie ca.. (Log2 N) die Schritte zum Beendigungszustand zu erhalten, wodurch die Gesamtkosten des Algorithmus ist O (log 2 n). Sie können den dn Teil ignorieren, wie es für jeden Schritt ein konstanten Zeitbetrieb ist.

Beachten Sie, dass wie bereits erwähnt, wird das Problem nicht unbedingt beenden, da ein willkürlicher Wert von Halbieren n wiederholt unwahrscheinlich ist, genau getroffen 1. Ich vermute, dass die T (n / 2) Teil sollte eigentlich lesen T (Etage (n / 2)) oder so etwas, um zu gewährleisten, dass diese beendet.

Answer 4

Theorem Verwendung Master finden Sie unter http://en.wikipedia.org/wiki/Master_theorem

Durch die Art und Weise, das asymptotische Verhalten des erneuten Auftretens ist O (n) unter der Annahme, d positiv und ausreichend kleiner als n (Größe des Problems)