我正在解决大西塔表示法的问题。我知道大 O 表示法表示最坏情况和上限,而 Omega 表示法表示最好情况和下限。
如果给我一个运行时间为 O(nlogn) 且时间为 Omega(n) 的算法,我将如何推断 Theta 等于多少?我开始假设当且仅当 O 和 Omega 相等时存在 theta 表示法,这是真的吗?
最佳答案
假设您的算法在 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 是否选择得太低。
关于notation - 求解 Big Theta 表示法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10405068/