質問
次の例を考えてみましょう。
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)
しかし、これについては結論が出せませんでした。次のステップで何をすればいいのか迷っています。
解決
あなたのアプローチは健全ですが、あなたは少し異なり、それを書き換える場合は、あなたが何をすべきかわかります:
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
が無限大になる傾向があり、何が起こるか見てみましょう。あなたは等比級数に精通している場合、それは役立つだろう。
他のヒント
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のために解決したい。
所属していません StackOverflow