解决一再发生关系使用的迭代方法

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 = 2 *（1 + 7/8 +（7/8）^ 2 + ...（7/8）^ Z）+ T（1）其中Z =？

唯一的问题是找到Z.我敢打赌，日志会有所帮助。很抱歉它是晚了，我不打算直接，但是......你不应该需要添加多个2N。

编辑：Z是你需要多少时间7/8，直到你得到1至多个N-

所以，N * 7 ^ Z / 8 ^ Z = 1

（7/8）^ Z = 1 / N

（8/7）^ Z = N

您想解决针对z。

Answer 3

你得到了什么没有在最后一个 几何级数 并且有是一个 公式 为了简化这种的总和。