Theta 符号的简单英文解释是什么？尽可能少的正式定义和简单的数学。
theta 表示法与 Big O 表示法有何不同？谁能用简单的英语解释一下？
在算法分析中有怎么用？我很困惑？
问问题
2603 次
2 回答
6
如果一个算法的运行时间是 Big Theta(f(n))，那么它的上下边界是 f(n)。大 O 是相同的，只是界限只在上面。
直观地说，Big O(f(n)) 表示“我们可以肯定，忽略常数因素和项，运行时间永远不会超过 f(n)。” 粗略地说，如果您认为运行时间“很糟糕”，那么 Big O 就是最坏的情况。Big Theta(f(n)) 说“我们可以肯定，忽略常数因素和项，运行时间总是随着 f(n) 而变化。” 换句话说，Big Theta 是一个已知的紧界：它既是最坏的情况，也是最好的情况。
直觉的最后一次尝试：大 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)。
于 2012-09-08T17:34:16.643 回答
2
我一直想用简单的话把它写下来。这是我的尝试。
如果算法的时间或空间复杂度表示为
Big O : Ex O(n) - 表示 n 是上限。最终值可能小于或等于 n。
Big Omega：Ex Ω(n) - 表示 n 是下限。最终值可以等于或大于 n。
Theta : Ex Θ(n) - 表示 n 是唯一可能的值。（上限和下限）
于 2013-06-20T00:31:30.340 回答