notation - 求解 Big Theta 表示法

Question

我正在解决大西塔表示法的问题。我知道大 O 表示法表示最坏情况和上限，而 Omega 表示法表示最好情况和下限。

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

Answer 1

假设您的算法在 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 是否选择得太低。