algorithm - 从此递归公式中减去时间复杂度？

我在阅读一个时间复杂性计算相关的问题，但我不能评论那里（没有足够的代表）。
What's the time complexity of this algorithm for Palindrome Partitioning?
我有一个关于从第一方程到第二方程的问题：
现在可以为H（n-1）编写相同的表达式，然后替换为back
要简化：
h（n）=2 h（n-1）+o（n）====>式1
这就解决了
h（n）=o（n*2^n）====>式2
有人能举例说明他是如何从等式1中得到等式2的吗？谢谢您。

最佳答案

公式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)

关于algorithm - 从此递归公式中减去时间复杂度？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/36380115/