Как вычислить T (N) для этого алгоритма простых чисел FINDER

Question

Этого алгоритма поиска всех простых чисел ниже N

var f = function(n){ 
    var primes = [2]; //1 
    var flag; //1 
    for(var i=3; i<n; i+=2){ // (from 3 to n-1)/2 
     flag = true; //1 
     var startI = 0; // 1 
     for(var y=primes[startI]; y<=Math.sqrt(i); y=primes[++startI]){ // ??? 
      if(i%y === 0) // 1 
       flag = false; // 1 
     } 
     if(flag) // 1 
      primes.push(i); // 1 
    } 
    return primes; // 1 
} 

До сих пор мой анализ делается до первого цикла, я не знаю, как обращаться вторая сумма (та, которая использует primes.length и Math.sqrt).

Т (п) = 1 + 1 + сумма ((1+ 1+ ?? странно сумма ???), от я = 3 до п -1)/2 + 1 + 1

Я понимаю, как анализировать до второго вложенного цикла, я подозреваю, что вокруг журнала (N) или что-то подобное, но я хотел бы знать точное количество итераций ..

Вопросы:

• Как я могу обработать такой цикл, который использует массивы в памяти для i terate?
• Если невозможно получить точный номер, как я могу получить хорошее приближение?

Любая помощь приветствуется (ссылки на похожие случаи, книги и т. Д.).

Answer 1

Внутренний цикл итерации по массиву всех простых чисел ниже sqrt(i). Итак, вам нужно вычислить количество элементов в этом массиве. В случае массива простых чисел вы должны использовать приближения для π(i), количество простых чисел ниже i.

Огибать их можно по x/ln(x) или (намного лучше) по li(x). Подробнее details here.

Для анализа x/ln(x) было бы проще.

В общей сложности вы получите (при условии n = 2k+1)

 
T(n) = T(n-2) + O(sqrt(n)/((1/2)⋅ln(n))) = O(Σi = 1,...,k 2⋅sqrt(2⋅i+1)/ln(2⋅i+1)) 

Вы получаете рекурсивную формулу из внутренного цикла, который перебирает массив простых чисел, меньших sqrt(n) (аппроксимировать sqrt(n)/((1/2)⋅ln(n))), и работу, которую вы нужно сделать, чтобы зайти так далеко, представленный T(n-2).

Возможно, вы можете упростить это. Я не хочу получать удовольствие от вас :)

Подсказка: Возможно, вы можете использовать интеграл, чтобы получить приблизительную сумму. Но я думаю, что нет «хорошего» способа записать его.

Если вы забыли о -части, вы можете увидеть T(n) ∈ o(n3/2) и T(n) ∈ ω(n). Может быть, вы можете сделать лучше.

Как упоминалось в @vib, вы можете получить более плотную верхнюю границу O(n3/2/ln(n)). Но обратите внимание, что sqrt(n)/ln(n) - это только приблизительное число чисел ниже sqrt(n). Таким образом, вы получаете лучшие оценки с лучшими приближениями. Так как эти приближения не дают точного значения π(n), мы не можем сказать, что этот алгоритм работает в Θ(n3/2/ln(n)).