你好,我正在尝试通过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从哪里来的呢?
你好,我正在尝试通过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
n + n/2 + n/4 + ...
,这等于n * (1 + 1/2 + 1/4 + ...)
。2
。因此你的总和是2n
。所以复杂度是O(n)
。