计算递归关系 T(n) = n+ T(n/2)

Question

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

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

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

= n + n/2 + n/4 + ... + n/(2^(k-1)) + T(n/2^k)

->>>

而且我不知道如何继续变大哦公式。请帮助我

Answer 1

我假设存在某种您没有告诉我们的初始条件，例如 T(1) = 0。

如果是，答案是O(log n)。

想一想你会如何计算 T(2)、T(4)、T(8)、T(16) 等。每一个都只需要一个额外的步骤。

T(1) = T(2^0) calls the method recursively 0 times.
T(2) = T(2^1) calls the method recursively 1 time
T(4) = T(2^2) calls the method recursively 2 times
T(8) = T(2^3) calls the method recursively 3 times

换句话说，步数就是力量。这意味着您必须取对数才能得到答案。

计算递归关系 T(n) = n+ T(n/2)

calculating recurrence relation T(n) = n+ T(n/2)

recurrence