如何从 T(n) = T(n/2) + n 得到 O(n)？

Question

我知道用主定理我会得到 teta(n)，但我正在尝试以其他方式解决递归问题，例如：

T(n) = T(n/2) + n
T(n) = T(n/4) + 2n
T(n) = T(n/8) + 3n
.
.
.
T(n) = T(n/2^k) + kn
k=logn -> T(1) + **nlogn**

有什么问题？

Answer 1

T(n)=T(n/2)+n=T(n/2^2)+n/2+n=T(n/2^3)+n/2^2+n/2+n= ... =  
=T(n/2^k)+n/2^(k-1)+n/2^(n-2)+...+n=  
=T(n/2^k)+n*(1-(1/2)^k)/(1-1/2)=  
=T(n/2^k)+2*n*(1-(1/2)^k)<=  
<=T(n/2^k)+2*n

如果你知道 T 是一个定义为 (0,0+e) 的函数，对于一些小的 e>0，那么你可以得出 T 是 O(n) 的结论。

Answer 2

在 Foundations of Algorithms - Richard E. Neapolitan.pdf 的最后几章中，您找到了几种解决递归关系的方法。某种方式像： 1- 递归树 2- 改变变量和微分方程

你还可以看到link

Answer 3

从头开始求解递归关系涉及两个步骤：

以某种方式找到答案
证明它是正确的

"Somehow find the answer part" 可能很难。通常的方法是扩展一些术语并进行推断，就像 Rodojf 在另一个答案中所做的那样，graph/table 找出并观察它，或者识别一个熟悉的模式。对于您的示例，所有这些方法都非常有效。

让我们在 table 或图形中放置几个点（让 C = T(1)）：

 n  |  T(n)
===========
 1  |   C
 2  |   C + 2
 4  |   C + 6
 8  |   C + 14
16  |   C + 30

在我看来 T(n) = 2n - 2 + C

我们可以证明 T(2^x) = 2^x+1 - 2 + C 对于所有 x>= 都是正确的0 通过归纳：

如果x=0，则2^x+1 - 2 + C = C，所以T(2^x) = 2^x+1 - 2 + C, 来自table
对于任何 x，T(2^x) = 2^x+1 - 2 + C ⇒ T(2^x+1) = 2^x+1 - 2 + C + 2^x+1 = 2^(x+1)+1 - 2 + C，通过替换

所以公式对 n=2⁰ 是正确的，这意味着它对所有 n=2^x

为了涵盖 n 的所有其他值，您还应该注意在 n 和 2n 之间以及 n/2 和 n 之间总是有一些 2^x，并且它们的 T(2^x) 值绑定 T(n).

对于一个案例来说，这是相当多的工作...这就是为什么我们记得主定理，该定理已在所有与其匹配的案例中得到证明模式。

如何从 T(n) = T(n/2) + n 得到 O(n)？

How to get O(n) from T(n) = T(n/2) + n?

algorithm

recurrence