ループの複雑さのためのn * n（ネストされていない）

Question

ネストされたループを見たときのアルゴリズムの複雑さのパターンは一般にn^(m+1)で、mはループネストファクタ（ループ内のループ）です。

for (i=0; i<n*n; i++) { 
    ... 
} 

が複雑O(n^2)ある

しかし、この単純なケースについて

、？

それはforループネスト通常のためになるように実行の量は同じであるので。

Answer 1

forループの各反復で行われる作業をO（1）とすると、forループの複雑さは実際にはn^2回繰り返すのでO（n^2）です。はい、正確には、次のような複雑さがあると想定します。

for(i=0;i<n;i++) { 
    for(j=0;j<n;j++) { 
     ... 
    } 
}