n * n（非嵌套）for循環複雜度

Question

我知道查看嵌套循環時的算法複雜度模式通常是n^(m+1)，其中m是循環嵌套因子（循環內的循環）。

但對於這個簡單的例子，在那裏

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

是複雜O(n^2)？

因爲執行量與正常的嵌套for循環相同。

Answer 1

假設在for循環的每次迭代中完成的工作是O（1），那麼由於迭代n^2次，for循環的複雜度確實是O（n^2）。是的，你假設它會具有相同的複雜性：

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