0

根据我的研究：我被要求确定一个函数相对于另一个函数的复杂性。即给定f(n)和g(n)，确定O(f(n()。在这种情况下，我会替换值，比较它们并得出复杂度 - 使用O(), Theta and Omega notations.

但是，在 中substitution method for solving recurrences，每个标准文档都有以下几行：

• [Assume that T(1) = Θ(1).]

•Guess O(n3) . (Prove O and Ω separately.)

•Assume that T(k) ≤ ck3 for k < n .

•Prove T(n) ≤ cn3 by induction.

当没有给出其他（除了 f（n））时，我应该如何找到 O 和 Ω？我可能是错的（我，绝对是），欢迎提供上述任何信息。

上面的一些假设是针对这个问题的：T(n) = 4T(n/2) + n ，而步骤的基本轮廓是针对所有此类问题的。

4

1 回答 1

2

这种特定的重复可以通过主定理解决，但您可以从替换方法中获得一些反馈。让我们试试你最初的猜测cn^3。

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

假设我们选择c这样n <= cn^3/2对于所有相关n的，

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，这是我们想要的界限的大 Theta。这通常意味着我们需要猜测得更高。让我们试试cn^2。

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

起初，这看起来也很失败。然而，与我们对 的猜测不同n，赤字与界限本身相差不大。我们也许可以通过考虑形式的边界来关闭它cn^2 - h(n)， where his 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。

于 2013-04-17T14:10:47.527 回答