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++) { 
     ... 
    } 
}