我正在阅读关于 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 的?谢谢。
最佳答案
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)
关于algorithm - 从这个递归公式中扣除时间复杂度?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36380115/