algorithm - 渐近符号

Question

根据我的研究:我被要求确定一个函数相对于另一个函数的复杂性。即给定 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 ，而步骤的基本轮廓是针对所有此类问题的。

Answer 1

这个特定的递归可以通过主定理解决，但您可以从替代方法中获得一些反馈。让我们试试你对 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) 形式的界限来关闭它。 , 其中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 .