time - 立方体の上の Oh 表記

Question

アルゴリズムの時間計算量の計算について質問があります。入れ子になった for ループが 4 つある場合、O(n^4) のような表記は可能ですか?

Answer 1

簡単に言えば、答えはイエスです。4 つのネストされたループは (ループによっては) O(n ⁴ ) になる可能性があります。

3 次以上の複雑さを持つ多項式時間アルゴリズムはあまりありませんが、存在します。たとえば、よく知られている AKS 素数性テストは、元の定式化では O(k ¹² ) (k は入力数値の長さ) ですが、最近は k ^7.5に縮小されました。