c - 这段代码的复杂度(Big O)顺序是多少

Question

我最初认为复杂度是 O(n^3)，因为内部循环转到 i*i，但现在我认为复杂度是 O(n^2)，因为“break”语句。

你怎么看？

#include <stdio.h>

int main()
{
    int i,k,l,m;
    unsigned int j;
    l=0;
    for (i=3; i<65535;i+= 2) {
        k=1;
        for (j=3; j <= i*i; j += 2) {
            if (j==i) continue;
            if(i%j ==0) {
                k=0;
                break;
            }
         }
         if (k) { l++; }
     }
     printf("%i\n", l);
     return 0;
}

Answer 1

内部循环对于素数是 O(N^2)，但对于非素数很快(最坏的情况是 O(N^1/2)，因为您只需要搜索 sqrt(N))。

但是，与非素数相比，素数的数量很少。到 X 为止的素数的近似值是:X/log(X)，如本 reference link. 中所见。

所以把非素数当作无关紧要的，有 N/log(N) 个素数，每个内循环需要 O(N^2) 时间，所以总时间是 O(N^3/log(N) ).