Theta 符号的简单英语解释？

Question

什么是 Theta 符号的简单英文解释？使用尽可能少的正式定义和简单的数学。

theta 表示法与 Big O 表示法有何不同？谁能用通俗的英语解释一下？

在算法分析中有怎么用？我很迷惑？

Answer 1

如果算法的运行时间是 Big Theta(f(n))，则它的上下渐近边界为 f(n)。Big O 是相同的，只是界限仅在上面。

直观地说，Big O(f(n)) 表示“我们可以确定，忽略常数因子和项，运行时间永远不会超过 f(n)。” 粗略地说，如果您认为运行时间是“糟糕的”，那么 Big O 就是最坏的情况。Big Theta(f(n)) 表示“我们可以确定，忽略常数因子和项，运行时间总是随着 f(n) 而变化。” 换句话说，Big Theta 是一个已知的紧界：它既是最坏的情况，也是最好的情况。

直觉的最后尝试：Big O 是“片面的”。O(n) 运行时间也是 O(n^2) 和 O(2^n)。Big Theta 并非如此。如果你有一个 O(n) 的算法运行时间，那么你已经有证据证明它不是 Big Theta(n^2)。它可能是也可能不是 Big Theta(n)

一个例子是比较排序。信息论告诉我们排序至少需要天花板(n log n)次比较，而我们实际上已经发明了O(n log n)算法（其中n是比较次数），所以排序比较是Big Theta(n log n)。