4

この例を考えてみましょう:

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)

しかし、これについては結論を出すことができませんでした。次のステップで何をすべきか混乱しています。

4

3 に答える 3

6

あなたのアプローチは健全ですが、少し異なる方法で書き直すとどうなるかがわかります。

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では、無限大に注意して、何が起こるか見てみましょう。幾何級数に精通している場合に役立ちます。

于 2010-01-13T00:30:59.780 に答える
0

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

唯一の秘訣は Z を見つけることです。ログが役立つに違いありません。申し訳ありませんが遅くなりました。正直に考えていませんが... 複数の 2n を追加する必要はありません。

編集: Z は、1 になるまで n に 7/8 を掛ける必要がある回数です。

したがって、n * 7^Z / 8^Z = 1

(7/8)^Z = 1/n

(8/7)^Z = n

Z について解きたいとします。

于 2010-01-13T00:22:26.453 に答える
0

最後の行で得られたのは等比級数であり、そのような合計を単純化する公式があります。

于 2010-01-13T00:26:45.620 に答える