为什么此代码中的时间复杂度为O（n ^ 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); } 

Answer 1

通过递增2而不是1，您将执行以下N*N*(1/2) 。 使用大（O）表示法，你不关心常数，所以它仍然是N * N. 这是因为大（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。 如果增加发生在GP如2