Kann diese Rekursion jemand Hilfe lösen? [geschlossen]

Question

T(n) = 2T(n/2) + 0(1)

T(n) = T(sqrt(n)) + 0(1)

Im ersten verwende ich Substitutionsmethode für n, logn, etc; alle gaben mir falsche Antworten.
Recurrence Bäume. Ich weiß nicht, ob ich mich bewerben kann als die Wurzel eine Konstante sein wird

Kann jemand helfen?

Answer 1

Schauen wir uns die erste. Zunächst einmal müssen Sie T (Basisfall) kennen. Sie haben erwähnt, dass es eine Konstante ist, aber wenn man das Problem zu tun ist es wichtig, dass Sie es aufschreiben. Normalerweise ist es so etwas wie T (1) = 1. Ich werde das, aber Sie können verallgemeinern, was auch immer es ist.

Als nächstes herausfinden, wie oft man wieder auftreten (das heißt, die Höhe des Rekursionsbaum). n ist Ihr Problem Größe, so wie oft können wir immer wieder teilen n durch 2? Mathematisch gesehen, was ich, wenn n/(2^i) = 1? Abbildung es aus, halten auf ihn für später.

Als nächstes wird ein paar Auswechslungen tun, bis Sie beginnen, ein Muster zu bemerken.

T(n) = 2(2(2T(n/2*2*2) + θ(1)) + θ(1)) + θ(1)

Ok, ist das Muster, das multiplizieren wir T () mit 2 ein paar Mal, und Dividieren durch 2 n ein paar Mal. Wie oft? i mal.

T(n) = (2^i)*T(n/(2^i)) + ...

Für die großen ? Begriffe am Ende, verwenden wir einen netten Trick. Schauen Sie oben, wo wir ein paar Auswechslungen haben, und ignorieren die T () Teil. Wir wollen die Summe der ? Bedingungen. Beachten Sie, dass sie bis zu (1 + 2 + 4 + ... + 2^i) * θ(1) hinzufügen. Können Sie eine geschlossene Form für 1 + 2 + 4 + ... + 2^i finden? Ich werde Sie, dass man geben; es ist (2^i - 1). Es ist ein guter nur auswendig lernen, aber hier ist, wie man es aus Abbildung würde.

Wie auch immer, alles in allem, was wir bekommen

T(n) = (2^i) * T(n/(2^i)) + (2^i - 1) * θ(1)

Wenn Sie i früher gelöst, dann wissen Sie, dass i = log_2(n). Stecker, der in, einige der Algebra, und Sie erhalten bis zu

T(n) = n*T(1) + (n - 1)*θ(1). T(1) = 1. So T(n) = n + (n - 1)*θ(1). Welches ist n-mal eine Konstante plus eine Konstante plus n. Wir fallen Terme niedrigerer Ordnung und Konstanten, so ist es ? (n).

Prasoon Saurav ist direkt über die Master-Methode verwendet, aber es ist wichtig, dass Sie wissen, was die Rekursion sagt. Die Dinge zu fragen sind, wie viel Arbeit ich bei jedem Schritt tun, und was ist die Anzahl der Schritte für eine Eingabe von Größe n?

Answer 2

Verwenden Sie Master Theorem solche Rekurrenzrelationen zu lösen.

Let a sein, eine ganze Zahl größer oder gleich 1 und b ist eine reelle Zahl größer als 1. Sei c eine positive reelle Zahl und d eine nicht negative reelle Zahl. Bei einer Wiederholung der Form

• T (n) = a T (n / b) + n ^c .. wenn n> 1

• T (n) = d .. wenn n = 1

dann für n eine Potenz von b,

1. , wenn log _b a c )
2. , wenn log _b a = c, T (n) = T (n ^c log n),
3. , wenn log _b a> c, T (n) = T (n ^{log _b a} ).

1) T(n) = 2T(n/2) + 0(1)

In diesem Fall

a = b = 2;
log _b a = 1; c = 0 (da n ^C = 1 => C = 0)

So Fall (3) anwendbar ist. So T(n) = Θ(n):)

---

2) T(n) = T(sqrt(n)) + 0(1)

Es sei m = log ₂ n;

=> T (2 ^M ) = T (2 ^{M / 2} ) + 0(1)

Jetzt K Umbenennung (m) = T (2 ^m ) => K (m) = K (m / 2) + 0(1)

Anwenden Fall (2).

---

Answer 3

Für Teil 1 können Sie Master-Satz verwenden, wie @Prasoon Saurav vorgeschlagen.

Für Teil 2, nur die Wiederholung erweitern:

T(n) = T(n ^ 1/2) + O(1)         // sqrt(n) = n ^ 1/2
     = T(n ^ 1/4) + O(1) + O(1)  // sqrt(sqrt(n)) = n ^ 1/4
     etc.

Die Serie wird auf k Bedingungen bis n ^ 1/(2^k) <= 1, das heißt 2^k = log n oder k = log log n fortzusetzen. Das gibt T(n) = k * O(1) = O(log log n).

Answer 4

Lassen Sie uns einen Blick auf die erste Wiederholung, T (n) = 2T (n / 2) + 1. Die n / 2 ist unser Anhaltspunkt hier: jeder verschachtelten Term Parameter Hälfte ist, dass seine Eltern. Wenn wir also mit n = 2 ^ k beginnen, dann werden wir k Begriffe in Expansion, das jeweils Addieren von 1 zu der Gesamt, bevor wir unseren Basisfall getroffen, T (0). Unter der Annahme, T (0) = 1, können wir T (2 ^ k) sagen = k + 1. Nun, da n = 2 ^ k müssen wir k = log_2 (n) haben. Daher T (n) = log_2 (n) + 1.

Wir können den gleichen Trick, um Ihre zweite Wiederholung, T (n) = T gilt (n ^ 0,5) + 1. Wenn wir beginnen mit n = 2 ^ 2 ^ k wir k Bedingungen in unserer Expansion haben, jeder Zugabe 1 zu der Gesamtmenge. Unter der Annahme, T (0) = 1, wir T (2 ^ 2 ^ k) = k + 1. Da n = 2 ^ 2 ^ k k Wir müssen müssen = log_2 (log_2 (n)), also T (n) = log_2 (log_2 (n)) + 1.

Answer 5

Rekurrenzrelationen und rekursive Funktionen sowie sollten ab f (1) gelöst werden. Im Fall 1 T (1) = 1; T (2) = 3; T (4) = 7; T (8) = 15; Es ist klar, dass T (n) = 2 * n-1, die in O-Notation O (n).
Im zweiten Fall T (1) = 1; T (2) = 2; T (4) = 3; T (16) = 4; T (256) = 5; T (256 * 256) = 6; Es wird einige Zeit dauern, um herauszufinden, dass T (n) = log (log (n)) + 1, wobei log in Base 2. Offensichtlich dies O (log (log (n)) Beziehung ist.

Answer 6

Die meiste Zeit der beste Weg, eine Wiederholung zu behandeln ist der erneute Auftreten Baum zu ziehen und vorsichtig den Basisfall zu behandeln.

Doch hier werde ich Ihnen leichten Hauch gebe mit Substitutionsmethode zu lösen.

In Wiederholung erster Versuch Substitution n = 2^k In Wiederholung versucht zweiten Wechsel n = 2^2^k