algorithm - Big theta 介于 big o 和 big omega 之间，还是既是 big o 又是 big omega？

Question

Big theta 表示它既是大 o 又是大欧米茄。据我了解，大 o 是上限，这意味着对于任何大输入，复杂性不应超过大 o，而大欧米茄则相反。big theta 和 big o 和 big omega 是多少，这意味着如果我在图表中看到 big o 和 big omega 将是同一条线。或者换句话说，如果我们找到问题的解决方案，无论我们尝试的输入有多大或有多大，复杂性都是相同的。是这个意思吗？

标签： algorithmtimetime-complexitybig-o

Answer 1

对于两个函数 f(n) 和 g(n)，您有以下含义：

• f(n) = O(g(n)) ：这意味着存在一些常数 c>0，使得对于足够大的 n，f(n) < c*g(n)。非正式地，“f 不会比 g 增长得快”。
• f(n) = Ω(g(n)) ：这意味着存在一些常数 c>0，使得对于足够大的 n，f(n) > c*g(n)。非正式地，“f 的增长速度不会比 g 慢”。
• f(n) = Θ(g(n)) ：这意味着存在一些常数 c_1>0 和 c_2>0 使得对于足够大的 n，c_1*g(n) < f(n) < c_2*g( n)。非正式地，“f 的增长速度与 g 一样快”。

所以你看到 Θ 确实是 O 和 Ω，因为如果 f 的增长速度既不快也不慢于 g，那么它会以相同的速度增长（反之亦然）。