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

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). Согласны ли вы?

Answer 1

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

2. Бит "найти следующее простое число" всего O (n) всего amortized - вы будете двигаться дальше, чтобы найти следующее число только n раз в total , а не за шаг.Таким образом, вся эта часть алгоритма занимает только 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) битовых операций.

Answer 2

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

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

Answer 3

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

2. Я думаю, что верхний цикл можно оптимизировать, заменив 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;
           }
       }    
   }
   

Answer 4

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