Временная сложность алгоритма Решета Эратосфена
Из Википедии:
Сложность алгоритма
O(n(logn)(loglogn))битовые операции.
Как Вы прибываете в это?
То, что сложность включает loglogn термин говорит мне, что существует a sqrt(n) где-нибудь.
Предположим, что я выполняю решето на первых 100 числах (n = 100), предполагая, что, отмечая числа, поскольку составной объект занимает время (реализация массива), количество раз, которое мы используем mark_composite() было бы что-то как
n/2 + n/3 + n/5 + n/7 + ... + n/97 = O(n^2)
И найти следующее простое число (например, для перехода к 7 после вычеркивания всех чисел, которые являются кратными числами 5), количество операций было бы O(n).
Так, сложность была бы O(n^3). Вы соглашаетесь?
2 ответа
Ваше n / 2 + n / 3 + n / 5 +… n / 97 не равно O (n), потому что количество членов непостоянно. [Отредактируйте после вашего редактирования: O (n 2 ) слишком слабая верхняя граница.] Свободная верхняя граница равна n (1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 +… 1 / n) (сумма обратных значений всех чисел до n), что составляет O (n log n): см. Число гармоники . Более правильная верхняя граница - это n (1/2 + 1/3 + 1/5 + 1/7 +…), то есть сумма обратных чисел до n, которая равна O (n log log n). (См. здесь или здесь .)
Бит «найти следующее простое число» составляет всего O (n), амортизируется - вы переместитесь вперед, чтобы найти следующее число только n раз в итого , а не за шаг. Таким образом, вся эта часть алгоритма занимает всего O (n).
Таким образом, используя эти два, вы получаете верхнюю границу арифметических операций O (n log log n) + O (n) = O (n log log n). Если вы подсчитываете битовые операции, поскольку вы имеете дело с числами до n, они имеют примерно log n битов, и именно здесь учитывается коэффициент log n, давая O (n log n log log n) битовых операций.
То, что сложность включает термин loglogn, говорит мне, что где-то есть sqrt (n).
Имейте в виду, что когда вы находите простое число P во время просеивания, вы не начинаете вычеркивать числа в вашей текущей позиции + P ; вы фактически начинаете вычеркивать числа с P ^ 2 . Все числа, кратные P меньше, чем P ^ 2 , будут вычеркнуты предыдущими простыми числами.