algorithm - 如果一个算法在 theta 时间内运行，是否可能存在一个既小 o 又小 omega 的函数？

Question

如果一个算法在 theta 时间内运行，是否可能存在一个既小 o 又小 omega 的函数？

我知道如果函数有 theta 时间，则意味着它也有一个大的 o 和 omega 函数。

如果可能的话，你能举个例子吗？

Answer 1

不可以，little o 和 little omega 中不能同时存在一个这样的函数。

假设你的函数是f(x)。然后对于小 o f(x) ∈ o(g(x)) 跟随 g(x) 比 f(x) 增长得更快.类似地，如果 f(x) ∈ ω(g(x))，则 g(x) 比 f(x) 增长得慢得多.

因此:

o(f) ∩ ω(f) = ∅.

但是，对于 Theta:

f(x) ∈ Θ(g(x)) iff f(x) ∈ O(g(x)) and f(x) ∈ Ω(g(x))

所以对于f(x) ∈ Θ(g(n))，f(x) 必须都在 g(n) 的 Ω 和 O。

如果您还记得 little o 是 little ω 的逆，它可能也更容易理解。因此

f(x) ∈ o(g(x)) <=> g(x) ∈ ω(f(x))

作为旁注，little o 和 ω 在计算机科学中很少使用。大多数算法以大 Θ、O 或 Ω 运行。