解决Big Theta标记
我正在解决一个大的theta符号的问题。 我明白，大O符号表示最差的情况和上限，而欧米茄符号表示最好的情况和下限。
如果我得到一个运行在O（nlogn）时间和欧米茄（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可能选得太低。
链接地址: http://www.djcxy.com/p/6833.html