3

我在解决大 theta 表示法时遇到问题。我知道大 O 表示法表示最坏情况和上限，而 Omega 表示法表示最佳情况和下限。

如果给我一个在 O(nlogn) 时间和 Omega(n) 中运行的算法，我将如何推断 Theta 等于什么？我开始假设当且仅当 O 和 Omega 相等时才存在 theta 符号，这是真的吗？

4

1 回答 1

0

假设您的算法在f(x).

  • f(x) = O(n*log(n))意味着对于x足够高，有一些常数c1 > 0，所以f(x)总是小于c1*n*log(n)。

  • f(x) = Omega(n)意味着对于x足够高，有一些常数c2 > 0，因此f(x)将大于c2*n

    • 所以你现在所知道的是，从某个点开始（x足够大）你的算法将运行得比 快c2*n和慢c1*n*log(n)。

  • f(x) = Theta(g(x))意味着对于x足够大有一些c3 > 0等等c4 > 0，c3*g(x) <= f(x) <= c4*g(x)这意味着f(x)只会比 更快或更慢地运行一个常数因子g(x)。确实如此，f(x) = O(g(x))并且f(x) = Omega(g(x))。

    结论：仅给出 O 和 Omega，如果它们不相同，您将无法得出 Theta 是什么。如果您有算法，您可以尝试查看是否可能选择了 O 太高，或者可能选择了 Omega 太低。

    • 于 2012-06-03T22:25:32.820 回答