Алгоритм "Сито Эратосфена" по javascript

Question

Является ли код в примере реализации Решета Эратосфена?
В чем сложность этой реализации?

UPD: я строю диаграмму операции подсчета с элементом массива.И я думаю, что сложность составляет O(n).Я прав?

console.time('exec');
var arr = fn(Math.pow(10, 2));
console.timeEnd('exec');

function fn(n) {
    var arr = Array.apply(null, {length: n + 1}).map(function() {return true;});
    arr[0] = arr[1] = false;
    var base = 2;
    while (Math.pow(base, 2) < n) {
        var counter = 2;
        while (counter * base < n) {
            arr[counter * base] = false;
            counter++;
        }
        base++;
    }
    return arr;
}

// show result
arr.forEach(function(item, index) {
  if (item) {
     console.log(index);
  }
});

Answer 1

Асимптотическая временная сложность алгоритма, как мне кажется, O ( n log n ) .

Внешний цикл работает для 2 ... sqrt(n).Внутренний цикл выполняется n / base раз, где base находится во внешнем диапазоне 2 ... sqrt(n).

Выполнение циклов приводит к общему количеству итераций, которое может быть выражено как:

(1) (n / 2) + (n / 3) + (n / 4) + ... + (n / sqrt(n))

Вышеуказанные круглые скобки используются для обозначения числа итераций внутреннего цикла в пределах одной итерации внешнего цикла.

Мы можем извлечь n и получить

(2) n * (1/2 + 1/3 + 1/4 + ... + 1 / sqrt(n))

Заключенный в скобки термин - это ряд гармоник, который, как известно, расходится, поэтому мы не получаем ничего хорошего, как O (1) там, хотя расхождение чрезвычайно медленно.Это также подтверждается эмпирически вашей диаграммой, которая выглядит линейной.

Было показано, что ряд гармоник имеет постоянную связь с ln(n) ( source ).

Следовательно,мы получаем n * ln(n) и, следовательно, сложность O ( n log n ) .

Вы неполучение более приятной O ( n log log n ) сложности, поскольку ваше решение не использует простую факторизацию (и, следовательно, ряды простых гармоник O (журнал n ) ( source )).

Практически, это потому, что ваш алгоритмпроверяет не простые числа, например, тот же индекс в arr[counter * base] = false; назначен для пар base и counter {2, 6}, {3, 4}, {4, 3}, {6, 2}, но все же *Уже известно, что 1075 * 4 и 6 не являются простыми числами в той точке, в которой они применяются, и по определению алгоритма все их кратные также уже известны как не простые числа, и поэтому бесполезно проверять их снова.

РЕДАКТИРОВАНИЕ

An O ( n log log n ) Реализация JavaScript может выглядеть следующим образом:

function sieve(n)
{
    // primes[x] contains a bool whether x is a prime
    const primes = new Array(n + 1).fill(true);
    // 0 and 1 are not primes by definition
    primes[0] = false;
    primes[1] = false;

    function square(i)
    {
        return i * i;
    }

    for (let number = 2; square(number) <= n; number += 1)
    {
        if (!primes[number])
        {
            // we have already determined that the number is not a prime
            // therefore all its multiples are also already determined not to be primes
            // skip it
            continue;
        }

        for (let multiplier = 2; multiplier * number <= n; multiplier += 1)
        {
             // a multiple of prime is not a prime
             primes[multiplier * number] = false;
        }
    }

    return primes;    
}

Такой алгоритм все еще запускает внешний цикл sqrt(n) раз, но теперь внутренний цикл запускается не для каждого числа, а только для простых чисел, поэтому для (2) мы теперь получаем

(2a) n * (1/2 + 1/3 + 1/5 + 1/7 + ... + 1 / (last_prime_less_or_equal_sqrt(n))

Как упоминалось ранее, заключенный в скобки термин представляет собой последовательность простых гармоник с log log n ростом.Это приводит нас к O ( n log log n ) , умноженному на n .

Answer 2

@ ЗденекЖелинек, @NinaScholz, спасибо за вашу помощь.Это код, основанный на ваших предложениях.
Наконец, надеюсь, что мне удалось реализовать его со сложностью O (n log log n) .

console.time('exec');
var arr = fn(Math.pow(10, 5));

function fn(n) {
  var arr = Array.apply(null, {
    length: n + 1
  }).map(function(_, i) {
    return i > 1;
  });
  var base = 2;
  while (Math.pow(base, 2) < n) {
    var counter = 2;
    while (counter * base <= n) {
      arr[counter * base] = false;
      do {
        counter++;
      } while (!arr[base]);
    }
    do {
      base++;
    } while (!arr[base]);
  }
  return arr;
}
console.timeEnd('exec');
console.log('array length: ' + arr.length);

// show result
/*
arr.forEach(function(item, index) {
  if (item) {
    console.log(index);
  }
});
*/

Answer 3

Сложность времени выполнения O (n * n), потому что вы выполняете итерацию базы и получаете счетчик до требуемого значения n (где вы пропустили последнее значение в сравнениях для циклов).

console.time('exec');

function fn(n) {
    var arr = Array.from({ length: n + 1 }, (_, i) => i > 1),
        base = 2,
        counter;

    while (Math.pow(base, 2) <= n) {
        counter = 2;
        while (counter * base <= n) {
            arr[counter * base] = false;
            counter++;
        }
        base++;
    }
    return arr;
}

var arr = fn(Math.pow(10, 2));

console.timeEnd('exec');
// show result
arr.forEach(function(item, index) {
  if (item) {
     console.log(index);
  }
});