Comments 43
Вложенный цикл суммарно выполняет O(n) операций. Это как, допустим
step = n;
for (i = 0; i < n; ++i) {
step /= 2;
for (j = 0; j < step; ++j) {
do_somthing();
}
}Вложенный цикл выполнит n/2 + n/4 + n/8 +… операций. Cуммарно — меньше n.
Еще одна аналогия — обход в ширину графа c n ребрами (если ребра заданы списком смежности). Вроже бы опять 2 вложенных цикла, но внутренняя итерация суммарно выполнится на более n раз.
Внутренний цикл — O(n), внешний цикл — n…
Ну да, большинство итераций внешнего цикла не сделают почти ничего. Цикл for посмотрит на условие и не выполнит ни одну итерацию. Также и алгоритм в этой статье.
Что касается английской вики, там есть ссылка на тот же первоисточник с линейным алгоритмом, но самого алгоритма нет, да.
Я подозреваю, что этот алгоритм — плод народного творчества. Поэтому нигде не удалось найти объяснение алгоритма с доказательством.
Для n верхняя граница количества простых чисел в интервале [1,n] в первом приближении оценивается как ln(n). То есть, общая оценка алгоритма — O(n*log(n)).
Ну прочитайте же, пожалуйста, доказательство.
Внутренний цикл перебирает только простые меньше lp(i), что, например, для всех четных чисел — всего 2. Т.е. перебираются сильно меньше чисел.
Алгоритмы, где 2 вложенных цикла суммарно делают линейное количество операций встречаются довольно часто. Тот же KMP для поиска подстроки, или обход дерева в ширину.
Для n верхняя граница количества простых чисел в интервале [1,n] в первом приближении оценивается как ln(n). То есть, общая оценка алгоритма — O(n*log(n)).
Кстати, верхняя оценка количества простых — n/log n, а не log n, как вы написали.
А КМП и обход дерева в ширину реализуются без вложенных циклов, так что тут ваши примеры несколько неудачны.
А КМП и обход дерева в ширину реализуются без вложенных циклов, так что тут ваши примеры несколько неудачны.
Ну, КМП, допустим, можно реализовать через конечный автомат (кстати, моя вторая статья как раз про это в том числе). Но это немного другой алгоритм, да и я сомневаюсь, что вы это имели ввиду. Как обход в ширину делается без вложенных циклов — я вообще не в курсе.
Очень интересно. Могли бы вы привести наброски кода? И для кмп или хотя бы только для обхода в ширину.
var needle = "abracadabra";
var needle_pref = [0];
var i = 0;
var j = 1;
while (i < needle.length) {
if (needle[i] == needle[j]) {
needle_pref[i++] = ++j;
} else if (j == 0) {
needle_pref[i++] = 0
} else {
j = needle_pref[j-1];
}
}
var haystack = "abyrvalgabramabracadabracadabrass";
i = 0;
j = 0;
while (i < haystack.length) {
if (haystack[i] == needle[j]) {
if (j == needle.length - 1) {
console.log(i-j, haystack.substr(i-j, j+1));
i++;
j = needle_pref[j];
} else {
i++;
j++;
}
} else if (j == 0) {
i++;
} else {
j = needle_pref[j];
}
}В обходе дерева я действительно забыл про вложенный цикл записи потомков в очередь.
Ну покажите же, пожалуйста, цифры :)
Искать неточность в доказательстве сложнее, чем замерить производительность. У меня получилась нелинейная зависимость времени от n для вашего алгоритма:
Calculating -------------------------------------
1000 2.755k (± 3.9%) i/s - 13.860k in 5.038808s
10000 273.275 (± 2.9%) i/s - 1.378k in 5.046871s
100000 26.691 (± 3.7%) i/s - 134.000 in 5.027327s
1000000 2.590 (± 0.0%) i/s - 13.000 in 5.021461s
2000000 1.309 (± 0.0%) i/s - 7.000 in 5.349981s
Comparison:
1000: 2755.2 i/s
10000: 273.3 i/s - 10.08x slower
100000: 26.7 i/s - 103.23x slower
1000000: 2.6 i/s - 1063.97x slower
2000000: 1.3 i/s - 2105.49x slower# ruby
def fn(n)
pr = []
lp = Array.new(n)
2.upto(n) do |i|
unless lp[i]
lp[i] = i
pr.push i
end
pr.each do |p|
break unless p <= lp[i] && p * i <= n
lp[p * i] = p
end
end
pr
end
puts fn(100).join(' ')
require 'benchmark/ips'
puts Benchmark.ips { |x|
[1_000, 10_000, 100_000, 1_000_000, 2_000_000].each do |n|
x.report(n.to_s) { fn(n) }
end
x.compare!
}Если проблема в языке с GC, или в чем-то еще, покажите, пожалуйста, это вашими измерениями.
Eсли точно подсчитать, то сложность будет Θ((c1 — c2/logn) * n).
Это следует из того, что количество составных чисел ~ n — n/log n, а алгоритм выполняет действия для каждого из них.
Обратите внимание, эта сложность остается O(n), потому что с ростом n слагаемое c1*n доминирует над c2*n/logn.
Ваши же цифры вполне подходят под эту теорию — даже n log log n растет сильно быстрее, чем время работы вашего решения.
Плюс к этому, на больших массивах оно перестает влезать в кэш и работает медленнее.
Мерить точное время работы при скачках по 4-64Мб массиву — дело неблагодарное.
Давайте лучше подсчитаем количество операций:
long long Erato(unsigned int n) {
int cnt1 = 0, cnt2 = 0, cnt3 = 0;
vector<int> pr;
pr.reserve(n-1);
vector<int> lp(n+1);
unsigned int i, j;
long long sum = 0;
for (i = 2; i <= n; ++i) {
if (lp[i] == 0) {
lp[i] = i;
sum += i;
pr.push_back(i);
++cnt1;
}
int maxp = n / i;
for (j = 0; ++cnt3 && j < pr.size() && pr[j] <= lp[i] && pr[j] <= maxp; ++j) {
++cnt2;
lp[i*pr[j]] = pr[j];
}
}
cout << n << ' ' << cnt1 << ' ' << cnt2 << ' ' << cnt3 << '\n';
return sum;
}10 4 5 14
100 25 74 173
1000 168 831 1830
10000 1229 8770 18769
100000 9592 90407 190406
1000000 78498 921501 1921500
10000000 664579 9335420 19335419Как видите — все операции (и внутри цикла, и сравнение в цикле) выполняются меньше 2n раз. С ростом n все ближе к границе. Отсюда, вместе с несовершенством компьютеров, и получается небольшое замедление в ваших числах.
Тут есть Θ(N) умножений двух чисел длины log(N), то есть Ω(N * log(N)) битовых операций.
Модель такая же, как и для обычного решета — умножения происходят за константу.
Так-то, если битовую сложность считать, то за n надо брать не границу до которой ищутся простые числа, а ее длину. В такой модели сложность вообще будет O(2^n*n*log n). Еще и памяти n*2^n надо.
за n надо брать не границу до которой ищутся простые числа, а ее длину
А почему не длину этой длины, степенные башенки должны быть выше!
Если серьёзно, то длина это как раз граница до которой ищутся простые числа — n. Или КМП у вас работает за 2^n, а числа перемножаются за n*2^n?
У вас n — это граница до которой ищутся простые числа, зачем называть этой буквой ещё и её длину?
Что бы использовать привычную нотацию вида O(f(n)). Так-то можно обозначить такой буквой, какой мы захотим. Но тут вы правы, я зря Вас запутал этим.
В любом случае, если вы хотите считать битовые операции, то и стандартное решето будет не O(n*log log n), как везде написано, а O(n*log n*log log n), ведь там числа до n складываются.
Там нет умножений чисел размера O( log(n) ), только сложения-вычитания и прочие линейные операции, т.е. битовая сложность Θ( n * log(n) / log(log(n)) )
При сложности умножения Θ(n * log(n)) у вас битовая сложность Θ(n * log n * log log n), такая же как и у обычного решета Эратосфена.
Т.е. «сэкономиленные» log(log(n)) вы на самом деле спрятали в сложность умножения.
такая же как и у обычного решета Эратосфена.
Да, в этой модели вычислений — вы правы.
Была такая мысль, но я так и не придумал, как это сделать быстро.
Ведь для разных i использутеся разный префикс pr. Так что, мы можем много-много итераций не трогать конец списка. А потом должны как-то быстро подсчитать (pr[k]-pr[k-1])*i.
Или я вас не правльно понял?
Так как (pr[k]-pr[k-1]) = O(pr[k] ^ (2/3)) асимптотически мало, мы можем предпосчитать все нужные произведения (pr[k]-pr[k-1])*i и это будет асимптотически меньше чем последующие сложения pr[k]*i = pr[k-1]*i + (pr[k]-pr[k-1])*i.
Так как (pr[k]-pr[k-1]) = O(pr[k] ^ (2/3)) асимптотически мало,
Это все-равно 2/3 log n бит. Вы таким образом ускорите умножения, но не ассимптотически.
k — количество простых в цикле для данного i.
Предподсчёт тоже будем не в лоб умножать, а складывать.
Почему вы количество простых-то берете в степени? все теже итерации сделать предется, все столько-же i*p значений подсчитать. Да, теперь вместо умножения двух чисел в log n бит вы умножаете число в 2/3 log n бит (pr[k]-pr[k-1]) на число в log n бит (i). Все те же n умножений во всем алгоритме, но числа на 33% короче. На асимтотику не влияет.
Я думал k у вас — сколько раз внутренний цикл для данного i выполнится. Туда по определению записано ограничение i*p <= n. А теперь мне кажется, что k у вас количество простых в списке pr для данного i.
Но это все не важно. Суть в том, что то же самое количество значений i*p вам все-равно придется вычислить, ведь это все вычеркнутые по одному разу числа и их надо обязательно вычеркнуть.
Теперь вместо каждого умножения ip вы предлагаете делать prev + i(pr[j]-pr[j-1]), так? Количество умножений не изменилось, потому что мы считаем все те же значения. Сами умножения работают на на ~15% быстрее, потому что один из множителей на треть короче, но на асимптотику это не влияет.
Все i(pr[j]-pr[j-1]) мы предпосдчитали заранее
Вот этих комбинаций, реально используемых O(n) и будет. Ровно столько, сколько умножений делает наивный алгоритм.
Я не понимаю, как из размера разности между простыми числами следует, что понадобится меньше умножений. Ведь каждое используемое значение, которое мы предподсчитываем, делается умножением. А нужно нам в каждом внутреннем цикле все те же k, суммарно O(n).
Если вас не затруднит, хотя бы псевдокод вашего решения приведите, пожалуйста.
for (i=2; i<=n; ++i) {
if (lp[i]==0)
pr[++np] = lp[i] = i;
m = min(lp[i], n/i), d=0;
for (k=0; k<np && pr[k+1]<=m; ++k)
d = max(d, pr[k+1]-pr[k]);
for (j=1; j<=d; ++j)
a[j] = a[j-1]+i;
pi=0;
for (j=1; j<=k; ++j)
pi += a[pr[j]-pr[j-1]], lp[pi] = pr[j];
}
От n/i можно избавиться, но тогда код станет сложнее.
Шикарно вообще! Ни единого умножения. Вы — гений. Я вообще вас не правильно сначала понял.
Единственное, надо подумать, а не станет ли d сильно больше k? И не сломает ли это асимптотику? Ведь если для каких-то определенных значений k Ваш алгоритм может сделать сильно больше операций и если это k довольно часто встречается, то все может поломаться.
Кажется, что не должно, ведь разница между простыми до n в среднем log n. Но это в среднем. И судя по Вики эта разница всегда меньше количества простых. Надо только убедится, что так и будет для очень больших простых.
P.S. жаль, не могу вам плюс в карму поставить!
d = O(k ^ (2/3)), и это не самая лучшая известная оценка.
Есть Гипотеза Крамера, утверждающая, что d = O(log(m)^2) = O(log(k)^2)
Так что всё, кроме вычисления n/i, выполняется в сумме за O(n*log(n)) битовых операций. Ну а как справиться с n/i подумайте сами.
rd(x) < x ведь всегда, а не только если x ∉ P. Если x — простое, то rd(x) = 1 < x.
В примечании сразу после хабраката я указал, что на практике этот алгоритм работает плохо из-за огромных потребностей в памяти. Этот алгоритм используется прежде всего, когда надо иметь возможность раскладывать все числа до n на простые множители.
Но все же, если вы про 10-ое задание на Эйлере, то там надо подсчитать простые всего до 2 миллионов. Тут что линейное решето требует 0,02с, что стандартное 0.015с на моем компьютере. И вся разница объясняется необходимостью работать с 8mb памяти вместо 250kb.
Всё же 20мс на линейном решете мне кажутся не то чтоб самым реальным результатом, наверняка улучшали его, как минимум, если все числа > 2 крутить в цикле, то будут отжираться огромные куски времени проца на молочение впустую составных чисел.
Ну помилуйте, цикл до 2 миллионов срабатывает мгновенно. На олимпиадах всегда был такой прием — просто считаем операции, вроде присвоения, if-ов и т.д. В секунду таких 400-600 миллионов точно влезет. Тут же выполнится, дай бог 6-8 миллионов. Как раз 1/50-ая
Код и счетчики операций есть в этом комментарии. Никаких оптимизаций почти нет.
Потом, по-моему, вы что-то путаете. То что O(n log log n) работает за 15мс у вас вопросов не вызывает, а в то что O(n) работает за 20мс вы поверить не можете.
Решето Эратосфена за O(n). Доказательство