为什么此代码中的时间复杂度为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

通过递增2而不是1,您将执行以下操作N*N*(1/2).使用大(O)表示法,你不关心常数,所以它仍然是N*N. 这是因为大(O)符号引用了算法增长的复杂性.