以下算法的运行时间？

Question

分而治之算法通过将尺寸n划分为2个子问题（每个尺寸为n-1），并花费O（n）时间来组合它们的解决方案来解决问题。这个算法的运行时间是什么？

我不太清楚如何构造这个递归关系并确定运行时是什么。以下关系是否正确？

T（N）= 2T（N-1）+ O（n）的

如何，我可以得到从这个运行时，如果是这样？

非常感谢！

Answer 1

是的，你的递归关系正确地描述你的问题。为了使事情具体，让我们说的递推关系是：T(n) = 2T(n-1) + n（即+n而非+O(n)

然后，伸缩递推关系（假设T（0）= 0）

T(n) = n + 2(n-1) + 4(n-2) + 8(n-3) + ... + 2^n(n-n) 
    = (1 + 2 + 4 + ... + 2^n)n - (0*2^0 + 1*2^1 + ... + n*2^n) 
    = n*(2^(n+1)-1) - 2(n*2^n-2^n+1) 
    = 2^(n+1) - n - 2 

检查。这是正确的：

2T(n-1) + n 
    = 2(2^n - (n-1) - 2) + n 
    = (2^(n+1) - 2n + 2 - 4) + n 
    = 2^(n+1) - n - 2 
    = T(n)