Временная сложность алгоритма Сито Эратосфена

Из Википедия:

Сложность алгоритма O(n(logn)(loglogn)) бит.

Как вы достигаете этого?

Что сложность включает в себя термин loglogn, говорит мне, что есть 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). Согласны ли вы?

Ответы

Ответ 1

  • Ваш 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) в целом, amortized - вы продвигаетесь вперед чтобы найти следующее число только 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).

Ответ 2

Что сложность включает термин loglogn, говорит мне, что где-то есть sqrt (n).

Имейте в виду, что когда вы находите простое число P при просеивании, вы не начинаете перебирать числа в своей текущей позиции + P; вы фактически начинаете перебирать числа в P^2. Все кратные P меньше P^2 будут скрещены предыдущими простыми числами.

Ответ 3

  • Внутренний цикл выполняет шаги n/i, где i является простым = > целым сложность sum(n/i) = n * sum(1/i). Согласно первичной гармонике серия, sum (1/i), где i является простым числом log (log n). В всего, O(n*log(log n)).

  • Я думаю, что верхний цикл можно оптимизировать, заменив n на sqrt(n), поэтому общая временная сложность будет O(sqrt(n)loglog(n)):

    void isprime(int n)
{
    int prime[n],i,j,count1=0;
    for(i=0;i<n;i++)
    {
       prime[i]=1;
    }
    prime[0]=prime[1]=0;
    for(i=2;i<=n;i++)
    {
        if(prime[i]==1)
        {
            printf("%d ",i);
            for(j=2;(i*j)<=n;j++)
                prime[i*j]=0;
        }
    }    
}

Ответ 4

см. приведенное выше объяснение, внутренний цикл является гармонической суммой всех простых чисел вплоть до sqrt (n). Таким образом, фактическая сложность - это O (sqrt (n) * log (log (sqrt (n))))