0

我正在阅读 CLRS 的第 3 章，该章是关于运行时间的，并且想通过一些示例来工作。由于我没有参加算法课程，因此我需要求助于 www 寻求帮助。

1) n^2 = 大欧米茄(n^3)

我认为这种说法是错误的：如果最佳案例运行时间是 n^3，那么算法不可能是 n^2，. 即使是最好的情况也比这慢。

2) n + log n = Big-Theta (n)

我认为这个说法是对的，我们可以忽略 log n 的下限。这为我们提供了 Big-Oh (n) 的最坏情况运行时间。以及 Big-Omega (n) 的最佳情况运行时间。我不太确定这一点。一些更多的澄清将不胜感激。

3) n^2 log n =大哦 (n^2)

我认为 this.statement 是错误的：最坏情况下的运行时间应该是 n^2 log n。

4) n log n = Big-Oh (n sqrt (n))

因为 n log n < n sqrt (n) 可能是真的。不过不太确定。

5) n^2 - 3n - 18 = Big-Theta (n^2) 真的不知道...

6) 若f(n) = O(g(n))且g(n) = O(h(n))，则f(n) = O(h(n))。

由传递属性持有。

我希望有人可以详细说明我相当可能是错误的答案:)

4

1 回答 1

4

  1. 你是对的，但原因不是。请记住，Omega(n^3) 并不直接与算法相关，而是与函数相关。
    你正确的原因是：对于每个常数，c,N都有一些n>N这样的——n^2 < c * n^3因此不在n^2Omega(n^3)

  2. 你是对的。 n < n + logn < 2*n（对于足够大的 n），因此n + logn既是O(n)和Omega(n)

  3. 你是对的，但同样，不要在这里使用“最坏情况”。解释和证明指南将类似于1。

  4. 这是正确的，因为log(n)它渐近小于sqrt(n)，其余的紧随其后。

  5. 与1中的原理相同。使用相同的方法将是正确的。

  6. 正确的。

作为旁注：Omega(n)并不意味着“最佳情况下的运行时间n”，它意味着表示复杂性的函数（可以是最坏情况复杂性，最佳情况复杂性或平均情况复杂性，......）具有存在的条件Omega(n)。

例如 - 快速排序：

  • 在最坏情况分析下，它是Theta(n^2)
  • 而在平均案例分析下，它是Theta(nlogn)
于 2012-11-25T13:16:48.607 回答