递归关系: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 + ...).

你有一个几何系列的总和,等于2.因此你的总和是2n.所以复杂性是O(n).

PS这不叫伸缩.数学中的伸缩是指后续术语相互抵消.

Answer 2

答案不是 nlogn 而是简单的 n

T(1)=0

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

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

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

伸缩展开式总共有log(N)条语句

现在通过伸缩取消，

我们有 T(N) = T(1) + N + N/2 + N/4 + N/8 +.....+ 2

T(1) = 0

T(N) = N + N/2 + ..... + 2

这是一个具有 log(n) 项的几何级数，每项减半。

T(N) = N [ 1 - (1/2)^log(N)] / (1/2)

T(N) = 2N[1 - 1/N]

T(N) = 2N - 2

因此答案是 O(N)。