n*n(非嵌套)用于循环复杂度
n*n (not nested) for loop complexity
我知道在查看嵌套循环时算法复杂度的模式通常是 n^(m+1)
,其中 m 是循环嵌套因子(循环中的循环)。
但是这个简单的例子呢
for (i=0; i<n*n; i++) {
...
}
复杂度是O(n^2)
?
因为执行量与普通嵌套 for 循环的执行量相同。
假设 for 循环的每次迭代中完成的工作是 O(1) 那么 for 循环的复杂度确实是 O(n^2) 因为你迭代了 n^2 次。是的,您假设它的复杂性与以下内容相同:
for(i=0;i<n;i++) {
for(j=0;j<n;j++) {
...
}
}
我知道在查看嵌套循环时算法复杂度的模式通常是 n^(m+1)
,其中 m 是循环嵌套因子(循环中的循环)。
但是这个简单的例子呢
for (i=0; i<n*n; i++) {
...
}
复杂度是O(n^2)
?
因为执行量与普通嵌套 for 循环的执行量相同。
假设 for 循环的每次迭代中完成的工作是 O(1) 那么 for 循环的复杂度确实是 O(n^2) 因为你迭代了 n^2 次。是的,您假设它的复杂性与以下内容相同:
for(i=0;i<n;i++) {
for(j=0;j<n;j++) {
...
}
}