循环关系 : T(n) = T(n/2) + n

Question

嗨，我正在尝试通过伸缩来解决以下递归关系，但我被困在最后一步。

T(N) = T(N/2) + N              T(1)=0
T(N/2) = T(N/4) + N/2
T(N/4) = T(N/8) + N/4
...
T(2) = T(1) + 2

T(N)= T(1) + N + N/2 + N/4

我认为答案是 nlogn 但我不知道如何将上述解释为 nlogn。我可以看到我正在执行 logn 步骤，但是 n 来自哪里？

Answer 1

您已经完全正确地完成了所有操作，但无法找到总和。你得到:n + n/2 + n/4 + ... ，等于 n * (1 + 1/2 + 1/4 + ...) .

你得到了 geometric series ，等于 2 .因此你的总和是 2n .所以复杂度是O(n) .

附言这不称为伸缩。数学中的伸缩是随后的术语相互抵消。