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

Question

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

сложность алгоритма
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). вы согласны?

982 4

performance algorithm time-complexity sieve-of-eratosthenes

4 ответов:

Comments

Ничего не найдено.

ShreevatsaR · Accepted Answer · 2010-04-06 08:17:36

ваш n/2 + n/3 + n/5 + ... n / 97 не является O(n), потому что число членов не является постоянным. [Редактировать после редактирования: O (n²) слишком свободная верхняя граница.] Свободный верхний-предел Н(1+1/2+1/3+1/4+1/5+1/6+...1/н) (сумма обратных величин все числа до 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 N) битовые операции.

jemfinch · Accepted Answer · 2010-04-08 07:10:40

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

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

anand tripathi · Accepted Answer · 2015-08-16 20:26:49

внутренний цикл делает 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;
        }
    }    
}

Bharath Kumar Reddy Appareddy · Accepted Answer · 2018-07-08 13:38:38

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