#python #time-complexity #primes #space-complexity
Вопрос:
Мне дают целое число n и велят вернуть все простые числа от 1 до n.
Я знаю, что на этот вопрос здесь много раз отвечали, но мой вопрос касается двух методов отслеживания не простых чисел. Эти два метода являются:
- Создать
array of size n, где каждый индекс представляет собой число в диапазоне от 1 до n, и использоватьBoolean (i.e. True or False), чтобы пометить каждую запись, если она не является простым;the array is initially emptyно когда мы попали премьер, мы будем отмечать все кратные премьер-как false (т. е. не является простым) в массиве, так что, когда мы доберемся до количество нам не нужно, чтобы ‘проверить’ это если по простому. В противном случае мы «проверим», является ли число простым, попробовав по модулю от 0 до этого числа. - Создайте a
set()и повторите от 0 до n в соответствии с 1. и каждый раз, когда мы сталкиваемся с простым числом, храните все его кратные в этом наборе, и для каждого числа от 0 до n мы сначала проверяем, находится ли оно в этом наборе, прежде чем проверять, является ли оно простым или нет.
Есть ли какая-либо разница с точки зрения сложности времени и пространства с помощью вышеперечисленных двух методов?
Комментарии:
1. Исходя из правила ПОЦЕЛУЯ (пусть оно будет глупо простым), я бы выбрал массив (список на Python). Потому что a
set-гораздо более сложный контейнер, и он должен будет содержать все не простые числа. Кроме того, массив может быть выделен с самого начала, когда мы знаем, что выделение дорого. Но я не тестировал его на Python, следовательно, комментарий, а не ответ…2. Если бы набор содержал простые числа, а не простые, он должен был бы в конечном итоге выиграть в пространстве, так как большие простые числа удаляются друг от друга.
3. Вы можете уменьшить потребность в пространстве, сохранив отдельные биты, а не целое логическое значение (24 бита?). Это позволит вам хранить 24 результата в пространстве одного логического значения. Однако это может стоить вам времени на обработку.
Ответ №1:
TLDR: с точки зрения биг-О, они эквивалентны как во времени, так и в пространстве. Однако на практике существует существенная разница.
Временная сложность: мы обрабатываем все числа, устанавливая все кратные в обоих случаях (N/2 N/3 N/5 …). В обоих случаях установка флага занимает O(1) времени. В обоих случаях сложность пространства равна O(n).
Разница в том, что список занимает всего несколько байтов на логическое значение. Набор также занимает те же несколько байтов для хранения значения, но также должен хранить хэши ключей, вести записи о столкновениях и обрабатывать изменения размера. Хотя все это по-прежнему сводится к асимптотической сложности O(1), на практике она имеет существенный постоянный множитель, который необходимо учитывать.
Комментарии:
1. Спасибо, Марат, в этом есть большой смысл. Хотя я знаком с хэш-наборами/словарями, я не знал, что происходит в фоновом режиме, но в данном случае это очень полезно знать.