シータまたはリトルOの代わりにビッグ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

kがn<=k!のような最小の整数である場合、f(n)=k!とします。

そしてf(n)は（f(k!+1)/(k!+1)が無限大になる傾向があるため）いずれもθ(n)ません（f(k!)=k!ため）o(n)であるが、明確f(n)=O(n)（f(n)<=nとして）。