Какой порядок сложности (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)).

Answer 2

for (j=3; j <= i*i; j += 2) { if (j==i) continue; if(i%j ==0) { k=0; break; } }

Без J == я

здесь у = 3,5,7,9,11,13,15,17 .... 65535. Это означает, что j будет содержать все простые числа до 65535, отличные от 2. Здесь есть математика. j < i * i. если i - степень 2 или простое число, то j цикл будет выполнен полностью, но мы можем пренебречь степенью 2, поскольку i всегда нечетно. Для любого i в некоторой точке i = j [O (n) сложность]

Если i является согласным, тогда i% j == 0 произойдет быстро. Как указано JS1, j-цикл будет принимать n/logn, пренебрегая j == i.

Так общая временная сложность = O (N * 2/LOGN)