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(...)什么时候θ(...)或 o(...)是更强的描述符吗？

Answer 1

让f(n)=k! , 当 k是满足 n<=k! 的最小整数.

然后f(n)不是 θ(n) (因为 f(k!+1)/(k!+1) 趋于无穷大)o(n) 也不是(自 f(k!)=k! 起)，但显然 f(n)=O(n) (如 f(n)<=n )。