algorithm - T(N) = 2T(N − 1) + N, T(1) = 2 的大 O

Question

如何为此获得 big-O？

T(N) = 2T(N − 1) + N, T(1) = 2

我得到了两种答案 O(2^N) 或 O(N^ 2)，但我不知道如何正确解决

Answer 1

将 T(N) 除以 2^N 并命名结果:

S(N) = T(N)/2^N

根据T(N)的定义我们得到

S(N) = S(N-1) + N/2^N                                  (eq.1)

意味着 S(N) 增加，但很快收敛到一个常数(因为 N/2^N -> 0)。所以，

T(N)/2^N -> constant

或

T(N) = O(2^N)

---

详细证明

在下面的评论中，Paul Hankin 建议如何完成证明。取 eq.1 并从 N=2 求和到 N=M

sum_{N=2}^M S(N) = sum_{N=2}^M S(N-1) + sum_{N=2}^M N/2^N
                 = sum_{N=1}{M-1} S(N) + sum_{N=1}^{M-1} (N-1)/2^{N-1}

因此，在取消索引为 N = 2、3、...、M-1 的项后，我们得到

S(M) = S(1) + sum_{N=1}^M N/2^N - M/2^M

并且由于右侧的级数收敛(因为它的项以 1/N^2 为界，N>>1 已知会收敛)，S(M) 收敛于一个有限常数。