递归关系：T(n) = T(n/2) + n。

Question

你好，我正在尝试通过telescoping解决以下递归关系，但我卡在了最后一步。

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从哪里来的呢？

- Harry Tiron

Answer 1

你做的一切都是正确的，但是没有找到一个总和。你得到了：n + n/2 + n/4 + ...，这等于n * (1 + 1/2 + 1/4 + ...)。

你得到一个几何级数的总和，它等于2。因此你的总和是2n。所以复杂度是O(n)。

P.S. 这不叫做望远镜式消除法。在数学中，望远镜式消除法是指后续项相互抵消。

- Salvador Dali

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)。

- phoenyx

---

T（1）不应该是1吗？ - Richard