Сложность времени сита эратешешен алгоритма

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

Таким образом, используя эти два, вы получаете верхнюю границу O (N Log Log N) + O (N) = O (N Log Nog N) арифметических операций. Если вы считать битовые операции, поскольку вы имеете дело с числами до N, они оказываются о журналах N Bits, где фактор журнала N приходит, давая o (n log n log log n) битных операций.

Answer 2

То, что сложность включает в себя термин логпогнала, говорит мне, что где-то есть SQRT (N).

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

Answer 3

1. Внутренняя петля делает n/i Шаги, где i является Prime => целая сложность 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). Итак, фактическая сложность IS O (SQRT (N) * log (log (sqrt (n))))))