为什么不存在小θ渐近符号？

Question

这个问题是我们的教授问的，我不明白为什么小 theta 不存在/我想我明白这一点，但是我们如何从数学上证明它不存在。

Answer 1

定义：

Big O：算法运行时的上限。

Big Theta (?)：这是一个“紧”或“精确”界限。它是 Big O 和 Big Omega 的组合。

Big Omega (?)：算法运行时间的下限。

小 o：算法运行时间的上限，但渐近运行时间不能等于上限。

Little Omega (?)：算法运行时间的下限，但渐近运行时间不能等于下限。

像这样想

o(n) = O(n) - ?(n)（我们不能“触及”上界）
?(n) = ?(n) - ?(n)（我们不能“触及”下界边界）

如果我们也一样

?(n) = ?(n) - ?(n)

我们基本上会说运行时无法触及我们为其设置的确切界限……这是不可能的，因为它是一个确切界限。运行时肯定会“触摸”它。

我们如何在数学上证明它不存在

没有算法可以采用的运行时不会与精确边界相交。因此，属于一个理论上的小 theta 的所有运行时的集合将是空集。

Answer 2

从定义中可以看出，little-oh 和little-omega 的交集有一个空集。