recursion - 求解具有多个递归步骤的递归方程

Question

我正在研究一些算法，并试图确定在形成方程时如何处理多个递归步骤。

所以展览A：

对我来说很明显，这里的递归方程是： T(n) = c + 2T(n/2) 在大 O 表示法中简化为 O(n)

然而在这里，我们也有类似的事情发生，我得到了递归方程 T(n) = n + 2T(n/2) 因为我们有两个递归调用与第一个不同，在大 O 表示法中简化为 O (n)，但是这里不是这样。关于如何在第二个中获得正确的递归方程的任何输入？

任何关于如何解决这个问题的意见都会很棒。

Answer 1

您可能对主定理感兴趣：

http://en.wikipedia.org/wiki/Master_theorem

递推方程T(n) = n + 2T(n/2)是Theta(n log n)，可以使用定理推导出来。要手动执行此操作，您还可以假设n = 2^k并执行以下操作：

T(n) = 2T(n/2) + n
     = 2(2T(n/4) + n/2) + n
     = (2^2)T(n/(2^2)) + 2n
     = (2^2)(2T(n/(2^3)) + n/(2^2)) + 2n
     = (2^3)T(n/(2^3)) + 3n
     = ...
     = (2^k)T(n/(2^k)) + kn
     = nT(1) + n log2 n
     = Theta(n log n)