math - 我需要帮助来解决此问题

Question

我一直在尝试解决这种重复几乎 2 小时，但无法得到答案......

让：

T(n)= kn+T(n/2) for n>1 and T(1)=1 where n = 2^k for some integer k 

证明 T(n)= O(n)

Answer 1

（我假设T(n) = kn + T(n / 2) 中的 k 与 n = 2^k 中的 k 不同。如果这是错误的，我会更新这个。）

如果你只需要一个渐近界，那么你可以使用Master Theorem。你的复发是

T(n) = T(n / 2) + kn

所以 a = 1，b = 2 和 c = 1。因此，由于 log _b a = 0 < 1，主定理导致它求解为 Θ(n)。

如果你需要一个精确的值，你可以使用迭代方法来得到一个很好的猜测。我假设 T(1) = 1。

T(n) = T(n / 2) + kn

= (T(n / 4) + kn/2) + kn

= T(n / 4) + kn + kn/2

= (T(n / 8) + kn / 4) + kn + kn / 2

= T(n / 8) + kn + kn / 2 + kn / 4

...

= T(n / 2 ⁱ ) + kn(1 + 1/2 + 1/4 + ... + 1/2 ⁱ )

_{这在 i = log 2} n时终止，此时我们得到

T(n) = T(1) + kn(1 + 1/2 + 1/4 + ... + 1/n)

= 1 + kn(1 + 1/2 + 1/4 + ... + 1/n)

= 2kn

所以确切的数字应该是（模数学误差）2kn，与主定理的结果一致。

希望这可以帮助！