Lösen der Wiederkehrbeziehung T (n) = T (n-1) * T (n-2) + c wobei T (0) = 1 und T (1) = 2

Ich muss die Rekursionsbeziehung fürLösen der Wiederkehrbeziehung T (n) = T (n-1) * T (n-2) + c wobei T (0) = 1 und T (1) = 2

lösen

T(n) = T(n - 1) * T(n - 2) + c where T(0) = 1 and T(1) = 2.

der Algorithmus berechnet ^{2 f (n)} wobei f (n) die n-te Fibonacci-Zahl. Ich gehe davon aus, dass T (n - 2) bis T ungefähr gleich (n - 1) und dann I die Beziehung als

T(n) = T(n - 1)^2 + c

und die Wirksamkeit von neu schreiben I zu erreichen Komplexität von O (n). Dies ist der Algorithmus:

Power(n): 
    if n == 0 then x = 1; 
    else if n == 1 then x = 2; 
    else x = Power(n - 1) * Power(n - 2); 
    return x;

Ist es wahr, dass die Rekursion T (n) = T (n - 1) * T (n - 2) + c hat O (n) Komplexität?

Quelle

2016-05-13 Hesam E

Ihr Code benötigt O (2^N) Zeit. – zmbq

Sie verwechseln die Multiplikation im Algorithmus mit der Multiplikation in der Rekursionsbeziehung. Sie berechnen Power(n - 1) und Power(n - 2) und multiplizieren sie, aber dies dauert nicht T(n - 1) * T(n - 2) Zeit. Diese Werte werden separat berechnet und dann multipliziert, wobei T(n - 1) + T(n - 2) Mal angenommen wird, wobei eine Multiplikation mit konstanter Zeit angenommen wird.

Die Wiederholung wird dann T(n) = T(n - 1) + T(n - 2) + c. Wir werden das durch Substitution lösen. Ich überspringe die Wahl eines n ; Unsere Induktions-Hypothese lautet T(n) = d * 2^n - 1. (Wir brauchen -1, um später die c löschen zu können; dies wird als Verstärkung der Induktionshypothese bezeichnet, siehe beispielsweise here).

T(n) = T(n - 1) + T(n - 2) + c 
    = d * (2^(n - 1) - 1) + d * (2^(n - 2) - 1) + c (substitute by IH) 
    = 3d * 2^(n - 2) - 2d + c 
    <= d * 2^n - 2d + c         (3 < 2^2) 
    <= d * 2^n           (when d > c/2)

Fazit: T (n) ∈ O (2 n ).

Bonus Tatsache: die enge Grenze ist eigentlich Θ (φ ⁿ), wo φ ist das goldene Verhältnis. Eine Erläuterung finden Sie unter this answer.

Quelle

2016-05-13 19:49:50

@Jori. Vielen Dank, du hast recht, aber wenn es eine Multiplikation im Algorithmus gibt, wird die Rekursionsbeziehung auch eine Multiplikationsform sein. Es war mein Missverständnis :).Wenn also T (n) = T (n-1) + T (n-2) + c ist, ist es gleich der Fibonacci-Beziehung, wobei unter Berücksichtigung von T (n-2) ≈T (n-1) das obere Ergebnis erhalten wird gebunden als Ω (2^n) und wenn wir T (n-1) ≈T (n-2) betrachten, erhalten wir die untere Schranke als θ (2^(n/2)). Habe ich recht? ;) –

Danke auch für die Bearbeitung der Frage;) –

@HesamE, nein, für zwei Konstanten, C, D> 1 haben wir das O (C^n) = O (D^n), einfach weil 'C = D^{log_D C} 'und so' C^n' = D^{n * log_D C} '. Aber die Grenze von C^n/D^{n * log_D C} geht ins Unendliche, wenn n ins Unendliche geht. – blazs

Zuerst ist die Wiederholung, die die Laufzeit modelliert T(n) = T(n-1) + T(n-2) + C für T(1) = T(0) = 1, für einige C>0. Dies liegt daran, dass Sie zwei rekursive Aufrufe vornehmen, einen unter n-1 und den anderen unter .

Die Wiederholung, die Sie haben, ist genau das Fibonacci recurrence, wenn wir die zusätzliche Konstante vergessen (die am Ende einen Faktor C beitrug). Die exakte Lösung ist dies (Bildquelle: Wikipedia):