问渐近符号

EN

这种特殊的递归是可以通过主定理求解的，但您可以从替换方法中获得一些反馈。让我们尝试一下您对cn^3的初步猜测。

T(n)  = 4T(n/2) + n
     <= 4c(n/2)^3 + n
      = cn^3/2 + n

假设我们选择c，以便所有相关n的n <= cn^3/2，

T(n) <= cn^3/2 + n
     <= cn^3/2 + cn^3/2
      = cn^3,

所以T就是O(n^3)。这个推导过程中有趣的部分是，我们使用了一个三次项来消除线性项。像这样的过度杀伤力通常是一个迹象，表明我们可以猜得更低。让我们试试cn。

T(n)  = 4T(n/2) + n
     <= 4cn/2 + n
      = 2cn + n

这行不通的。右边和我们想要的界限之间的差距是cn + n，这是我们想要的界限的大θ。这通常意味着我们需要猜测得更高。让我们试试cn^2。

T(n)  = 4T(n/2) + n
     <= 4c(n/2)^2 + n
      = cn^2 + n

乍一看，这看起来也是一个失败。然而，与我们对n的猜测不同，赤字本身并不是很大。我们也许可以通过考虑cn^2 - h(n)形式的边界来结束它，其中h是o(n^2)。为什么要减法呢？如果我们使用h作为候选边界，我们将运行赤字；减去h，我们将运行盈余。h的常见选择是低阶多项式或log n。让我们试试cn^2 - n。

T(n)  = 4T(n/2) + n
     <= 4(c(n/2)^2 - n/2) + n
      = cn^2 - 2n + n
      = cn^2 - n

这恰好是递归的精确解决方案，这对我来说是相当幸运的。如果我们猜到了cn^2 - 2n，我们就会有一些剩余的积分。

T(n)  = 4T(n/2) + n
     <= 4(c(n/2)^2 - 2n/2) + n
      = cn^2 - 4n + n
      = cn^2 - 3n,

它比cn^2 - 2n稍微小一点。