如果一个算法在 theta 时间内运行，是否可能存在一个既小 o 又小 omega 的函数？
If an algorithm runs in theta time, is it possible for there to be a function that is little o and little omega as well?
如果一个算法在theta时间内运行，是否有可能存在一个小o和小omega的函数？
我知道如果函数有 theta 时间，则意味着它也有一个大的 o 和 omega 函数。
如果可以，能否举个例子。
不行，小o和小omega不可能同时有一个这样的功能。
假设你的函数是 f(x)。然后对于 little 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 ω 的 inverse，它可能也更容易理解。因此
f(x) ∈ o(g(x)) <=> g(x) ∈ ω(f(x))
作为旁注，little o 和 ω 在计算机科学中很少使用。 Big Θ、O 或 Ω.
中的大多数算法 运行
如果一个算法在theta时间内运行，是否有可能存在一个小o和小omega的函数？
我知道如果函数有 theta 时间，则意味着它也有一个大的 o 和 omega 函数。
如果可以，能否举个例子。
不行，小o和小omega不可能同时有一个这样的功能。
假设你的函数是 f(x)。然后对于 little 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 ω 的 inverse，它可能也更容易理解。因此
f(x) ∈ o(g(x)) <=> g(x) ∈ ω(f(x))
作为旁注，little o 和 ω 在计算机科学中很少使用。 Big Θ、O 或 Ω.