big-o - 说函数 f(n) = n 是 theta(n) 是否有效？

Question

我正在上课，我们正在查看时间复杂度信息。

我知道大 o 是一个上限，而欧米茄是一个下限，如果它们相同，那么函数就是 theta（那个界限）。

假设我有函数 f(n) = n。我们可以说那是 theta(n) 吗？

我认为这是因为对于 k>=1，C=1 是 O(n) 和 Omega(n)，但我想问一下。

标签： big-o

Answer 1

对，那是正确的。说f \in \Theta(g)ifff \in \Omega(g)和是一个常见的定义f \in O(g)。

这里f(n) = n和g(n) = n。

证明两个单独的部分，liminf f(n)/g(n) = liminf 1 = 1 > 0和limsup g(n)/f(n) = limsup 1 = 1 < \infty。

尤其f \in Theta(f)适用于所有功能f。

但是请注意，该符号通常使用大的\Theta，而不是小的。