algorithm - 何时使用 Big O 而不是 theta 或 little o

Question

关于渐近符号的问题。我看过很多关于渐近符号的解释说：

θ(...)类似于=

O(...)类似于<=

o(...)类似于<

这似乎暗示如果f(n) = O(g(n))，那么 要么f(n) = θ(g(n))要么f(n) = o(g(n))。

是否有可能f(n) = O(g(n))既没有f(n) = θ(g(n))也没有f(n) = o(g(n))？如果是这样，这有什么例子？如果不是，那我们为什么要使用O(...)whenθ(...)或o(...)are 更强的描述符？

Answer 1

让f(n)=k!, whenk是最小的整数，使得n<=k!。

那么f(n)不是θ(n)（因为f(k!+1)/(k!+1)趋于无穷大）也不是o(n)（因为f(k!)=k!），而是很明显f(n)=O(n)（as f(n)<=n）。