Сито Эратосфена около приближения сложности

Я попытался дать более точное приближение к Сите Эратосфена.Сито Эратосфена около приближения сложности

Элементарные операции и веса, которые я использовал:

prime[p]   -> 1 operation 
m = p * p  -> 2 operations 
prime[m] = false -> 1 operation 
m = m + p  -> 2 operations

Мое доказательство:

Является ли мое доказательство верно? В литературе я нашел, что сложность - это O (nlog (log (n))) или O (nlog (log (n))/log (n)).

источник

2013-03-26 flatronka

После нескольких логарифмов манипуляций вы увидите, что 'O (nloglogn) == O (nloglog (SQRT (п)))'. – SomeWittyUsername

Можете ли вы показать мне? Я не вижу его прямо сейчас. – flatronka

Кроме того, ваше доказательство кажется неправильным: 1. Ваш внутренний цикл будет выполняться только в том случае, если индекс внешнего цикла отмечен как простой - вы игнорируете этот факт. 2. Я не вижу никакой связи между вашими (1) и (4), (5). Разделение суммы должно выглядеть совершенно иначе – SomeWittyUsername

Да, это правильно, O(nloglogn)==O(nloglog(sqrt(n))):

enter image description here

источник

2013-03-26 14:18:26 SomeWittyUsername

спасибо за ваше время и помощь: D, это прекрасный ответ, который я ожидал: D. – flatronka

Сито Эратосфена около приближения сложности

ответ

Смежные вопросы