big-o - 大きなO表記

Question

私はBigO表記について読んでいます。私が持っている本には、 n ²の複雑さがO（n ³）のクラスにある例があります。n ³はnに依存し、「取り除く」ことができるのは単なる定数乗数ではないため、これは私には論理的ではないように思われます。

これら2つが同じ複雑さである理由を説明してください。このフォーラムや他のフォーラムで答えが見つかりません。

Answer 1

Big O は、n の大きな値の上限を決定します。O( n ³ ) は O( n ² )より大きいので、n ²プログラムは O( n ³ ) のままです。また、O( n ⁴ )、O(*n ⁵ )、...、O( n ^infinity ) です。

ただし、その逆は当てはまりません。n^3 プログラムは O( n ² ) ではありません。むしろ、Omega が下限 (少なくともどれだけの作業をしなければならないか) を決定するため、 Omega( n ^{2 ) になります。}

Big O は、この上限が「タイト」であることについては何も言っておらず、実際の複雑さよりも高くする必要があるだけです。したがって、n*n の複雑さのプログラムは O( n ³ ) によって制限されますが、これは厳密な制限ではありません。O( n ² ) はより厳密で、より有益です。