反復法を使用して漸化式を解く

Question

次の例を考えてみましょう。

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

T(1) = 0 と仮定しました

そして次の方法でそれを解決しようとしました

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)               

しかし、これについては結論が出せませんでした。次のステップで何をすればいいのか迷っています。

Answer 1

あなたのアプローチは健全ですが、あなたは少し異なり、それを書き換える場合は、あなたが何をすべきかわかります：

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

さて、kが無限大になる傾向があり、何が起こるか見てみましょう。あなたは等比級数に精通している場合、それは役立つだろう。

Answer 2

T（N）= T（7N / 8）+ 2N = 2N *（1 + 7/8 +（7/8）^ 2 + ...（7/8）^ Z）+ T（1）ここで、Z =？

唯一のトリックは、私はログが役立ちます賭けるZ.を見つけることです。申し訳ありませんが、それは遅れている、と私はまっすぐに考えていないのですが...あなたは複数2Nを追加する必要はありません。

編集：Zはあなたが1を得るまで7/8でのnを乗算する必要がありますどのように多くの時間です。

そこで、N * 7 ^ Z / 8 ^ Z = 1

（7/8）^ Z = 1 / N

（8/7）^ Z = N

あなたはZのために解決したい。

Answer 3

最後の行で得られたものは、 幾何級数 そして、 式 このような合計を単純化します。