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 是您需要将 n 乘以 7/8 直到得到 1 的次数。

所以，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 回答