以下算法的运行时间？

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)

以下算法的运行时间？

Runtime of following algorithm?

algorithm

complexity-theory

runtime

time-complexity