Lösen einer Rekursionsformel unter Verwendung Iterationsverfahren

Question

Betrachten Sie dieses Beispiel:

T(n) = T(7n/8) + 2n 

I T angenommen (1) = 0

und versuchte es in der folgenden Art und Weise zu lösen

T(n) = T(7n/8) + 2n
     = T(49n/64) + 2.(7n/8) + 2n
     = T(343n/512) + 2.(7n/8).(7n/8)+ 2.(7n/8) + 2n 
     = T(1) + 2n ( (7n/8)^i + ..... + 1)               

, aber ich konnte nicht zu einer Aussage über diese kommen. Ich bin verwirrt über das, was soll ich im nächsten Schritt zu tun.

Answer 1

Ihr Ansatz ist solide, aber Sie werden sehen, was zu tun ist, wenn man es etwas anders umschreiben:

T(n) = T((7/8)^1 * n) + 2 * (7/8)^0 * n
     = T((7/8)^2 * n) + 2 * (7/8)^1 * n + 2 * (7/8)^0 * n
     = T((7/8)^3 * n) + 2 * (7/8)^2 * n + 2 * (7/8)^1 * n + 2 * (7/8)^0 * n
     .
     .
     .
     = T((7/8)^k * n) + 2 * n * sum j = 0 to k-1 (7/8)^j

Nun, lassen Sie k bis Unendlich und sehen, was passiert. Es würde helfen, wenn Sie sich vertraut mit geometrischer Reihe .

Answer 2

T (n) = T (7n / 8) + 2n = 2n * (1 + 7/8 + (7/8) ^ 2 + ... (7/8) ^ Z) + T (1) wo Z =?

Der einzige Trick besteht darin, Z. Ich wette, ein Protokoll helfen. Leider ist es zu spät, und ich denke nicht gerade, aber ... Sie sollen nicht mehr 2n hinzufügen müssen.

Edit:. Z ist, wie viel Zeit, die du mehrfach n von 7/8 brauchen, bis Sie erhalten 1

So, n * 7 ^ Z / 8 ^ Z = 1

(7/8) ^ Z = 1 / n

(8/7) ^ Z = n

Sie möchten sich für Z lösen.

Answer 3

Was hast du in der letzten Zeile gibt es einen geometrische Reihe und es gibt ein < a href = "http://en.wikipedia.org/wiki/Geometric_series#Formula" rel = "nofollow noreferrer"> Formel eine solche Summe zu vereinfachen.