为什么这段代码的时间复杂度是O(n^2)？

Question

没看懂，为什么时间复杂度是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);
}

Answer 1

通过增加两个而不是一个，您正在执行以下

N*N*(1/2)

。使用 big(O) 表示法，您不关心常量，所以它仍然是 N*N。这是因为 big(O) 符号参考了算法增长的复杂性。

Answer 2

外循环将执行 n 次，对于每次外循环迭代，内循环将执行 n/2 次，因为 j +=2

Order = n×n/2 = n^2/2 =O(n^2) 因为常数不影响大 n

的运行时间

Answer 3

增量为 2，因此循环将运行 n/2。所以复杂度将是 n*n/2.

如果像 2 那样在 GP 中发生增量