11

Помогите разобраться со сложностью алгоритма. Пытался реализовать 'Решето Эратосфена'.

P.S. Насколько я понимаю первый цикл несмотря на continue имеет сложность sqrt(N), а вложенный log(N), получается итоговая sqrt(N)*log(N)?
P.P.S.Буду признателен за пример со сложностью log(log(N)).

Код функции ниже:

function filterOut(number) {
    var tempArray = new Array(number);
    var finalArray = [];
    var limit = Math.sqrt(number);
    for(var i = 2; i < limit; i++) {
        if(tempArray[i] != undefined) continue;
        else {
            for(var j=i; j*i < number; j++) {
                tempArray[j*i] = 0;
            }
        }
    }
    for(var i = 2; i < number; i++) {
        if(tempArray[i] != 0) finalArray.push(i);
    }
    return finalArray;
}
4
  • Если у вас получится - обязательно опубликуйте в каком-нибудь научном журнале! :-D Пример: log10(log10(1000)) == 0.4771 27 ноя 2017 в 18:34
  • Посмотрели решение?
    – user192664
    20 июн 2018 в 12:16
  • @Nikita Smith Да посмотрел и не понял к чему Вы(да еще и жирным шрифтом выделили подробное решение).Ваше решение отлично от моего тем,что Вы в цикле постоянно увеличиваете массив...посмотрите post scriptum. 20 июн 2018 в 18:00
  • На википедии описано доказательство сложности O(N*loglogN) и это доказательство применимо к вашему алгоритму.
    – EzikBro
    19 июл 2020 в 18:31

3 ответа 3

1

Для уменьшения сложности алгоритма исключите четные числа. Смысл в практических задачах их в решето добавлять, если только для демонстрации в учебных целях. И смысл хранить в виде массива int, разумнее в битовом массиве (существенно экономите память и ресурс движка на ее выделение). Ниже генератор использующий решето.

function Base(size) {
  this.arr = new Uint32Array(size);
}

Base.prototype.Add = function (num) {
  this.arr[num >> 5] |= 1 << (num & 31);
};

Base.prototype.isSet = function (num) {
  return (this.arr[num >> 5] & (1 << (num & 31))) !== 0;
};

let Max = 472882240;
let base = new Base((Max >> 5) + 1);

function init() {
  for (let i = 3; i < 21800; i += 2) {
    if (base.isSet(i)) 
      continue;
    for (let x = i + i; x <= Max; x += i) {
      base.Add(x);
    }
  }
}

class Primes {

  static *stream() {
    let num = 0;
    yield 2;

    for (let i = 3; i <= Max; i += 2)
      if (!base.isSet(i)) {
        yield i;
      }

  }

}

init();
-1

Предлагаю такую реализацию алгоритма "Решето Эратосфена (Sieve of Eratosthenes)" на javascript:

UPD: исправил код с учетом обсуждения в вопросе https://stackoverflow.com/questions/54614967/algorithm-sieve-of-eratosthenes-by-javascript

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);
  }
});
*/

-3

Подробное решение:

function eratosthenes(n) {
    var array = [], upperLimit = Math.sqrt(n), output = [];

    // Создаем массив от 2 до n-1
    for (var i = 0; i < n; i++) {
        array.push(true);
    }

    // Удаляем простые числа начиная с 2, 3, 5 ...
    for (var i = 2; i <= upperLimit; i++) {
        if (array[i]) {
            for (var j = i * i; j < n; j += i) {
                array[j] = false;
            }
        }
    }

    // Результирующий массив
    for (var i = 2; i < n; i++) {
        if(array[i]) {
            output.push(i);
        }
    }

    return output;
};

console.log(eratosthenes(100));

Вообще не знал до этого что за решето Эратосфена, но задачку решил. Наслаждайтесь!

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.