algorithm - 从这个递归公式中扣除时间复杂度？

Question

我正在阅读关于 SO 的时间复杂度计算相关问题，但我不能在那里发表评论(没有足够的代表)。 What's the time complexity of this algorithm for Palindrome Partitioning?

我有一个关于从第一个方程到第二个方程的问题:

Now you can write the same expression for H(n-1), then substitute back to simplify:

H(n) = 2 H(n-1) + O(n) =========> Eq.1

And this solves to

H(n) = O(n * 2^n) =========> Eq.2

谁能说明他是如何从 Eq.1 得到 Eq.2 的？谢谢。

Answer 1

Eq 1. 是一个 recurrence relation .请参阅有关如何求解这些类型方程的教程的链接，但我们可以通过如下展开来求解:

H(n) = 2H(n-1) + O(n)
H(n) = 2*2H(n-2) + 2O(n-1) + O(n)
H(n) = 2*2*2H(n-3) + 2*2O(n-2) + 2O(n-1) + O(n)
...
H(n) = 2^n*H(1) + 2^(n-1)*O(1) + ... + 2O(n-1) + O(n)

since H(1) = O(n) (see the original question)
H(n) = 2^n*O(n) + 2^(n-1)*O(1) + ... + 2O(n-1) + O(n)
H(n) = O(n * 2^n)