为什么这段代码的时间复杂度是O(n^2)？
Why is the time complexity O(n^2) in this code?
没看懂，为什么时间复杂度是O(n^2)而不是O(n*logn)？
第二个循环每次递增 2 所以不是 O(logn) 吗？
void f3(int n){
int i,j,s=100;
int* ar = (int*)malloc(s*sizeof(int));
for(i=0; i<n; i++){
s=0;
for(j=0; j<n; j+=2){
s+=j;
printf("%d\n", s);
}
free(ar);
}
通过增加 2 而不是 1，您将执行以下操作 N*N*(1/2)。使用 big(O) 表示法，您不关心常量，所以它仍然是 N*N。这是因为 big(O) 符号参考了算法增长的复杂性。
外循环将执行 n 次，对于每次外循环迭代，内循环将执行 n/2 次，因为 j +=2
Order = n×n/2 = n^2/2 =O(n^2) 因为常数不影响大 n
的 运行 时间
增量为 2，因此循环将运行 n/2。因此复杂度将为 n*n/2。
如果在 GP 中发生增量，如 2
没看懂，为什么时间复杂度是O(n^2)而不是O(n*logn)？ 第二个循环每次递增 2 所以不是 O(logn) 吗？
void f3(int n){
int i,j,s=100;
int* ar = (int*)malloc(s*sizeof(int));
for(i=0; i<n; i++){
s=0;
for(j=0; j<n; j+=2){
s+=j;
printf("%d\n", s);
}
free(ar);
}
通过增加 2 而不是 1，您将执行以下操作 N*N*(1/2)。使用 big(O) 表示法，您不关心常量，所以它仍然是 N*N。这是因为 big(O) 符号参考了算法增长的复杂性。
外循环将执行 n 次，对于每次外循环迭代，内循环将执行 n/2 次，因为 j +=2
Order = n×n/2 = n^2/2 =O(n^2) 因为常数不影响大 n
的 运行 时间增量为 2，因此循环将运行 n/2。因此复杂度将为 n*n/2。 如果在 GP 中发生增量，如 2