algorithm - Theta 符号的简单英语解释？

Question

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

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

算法分析中有怎么用到的？我很困惑？

Answer 1

如果算法的运行时间是 Big Theta(f(n))，则它在 f(n) 的上下渐进界限。大 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)

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