Вот только оно не работает, если перед циклом есть какой-то незацикленный отрезок. Еще встает вопрос, а как алгоритм разворота должен остановиться, ведь если цикл есть, то до конца не дойти никак.
Как только вы нашли какой-то элемент в цикле, то достаточно еще 2 раза пройти по списку, чтобы найти весь цикл. Сначала пройдитесь вперед, пока не вернетесь к известному элементу, узнав таким образом длину цикла. Затем пустите 2 указателя с разницей в длину цикла — они встретятся на первом элементе цикла.
Вы про квиксорт, который сортирует на месте в массиве? С разбиением по ведущему элементу? Там не так тривиально это разбиение делается — легко накосячить.
Да это же такой кладезь компромата! Просто представьте, сколько замечательных сюжетов можно пустить по НТВ, а то и по первому каналу, показывая в прайм тайм дикпики оппозиционеров.
От старых XUL расширений избавились, это так, но здесь, на сайте, где-то был очень хороший комментарий от разработчика расширений объясняющий, почему Мозилла пошла на такой шаг.
А нет ли у вас, случайно, ссылки на этот комментарий?
Еще раз: февраль 2013, TSLA 37$
февраль 2014 250$, т.е., в 6.75 раза или 575% годовых.
Ваш пример некорректен. Никто никогда не обещал такой доходности у Теслы. Повезло, совпало — вот и получилась такая доходность. Биткойн вон еще быстрее рос.
Если вы вложили деньги туда где вам обещали 10% плюс-минус, как повезет, а оно собрало 300% годовых — Вам очень повезло. Могло и не повезти. Если вам обещают 300% годовых — точно развод. Вопрос встает, почему бы тогда вместо привлечения Ваших денег тупо не взять кредит под 10%, получить 300% прибыли и заработать 190% самому? Если какая-то достаточно надежно работающая схема есть, то никто Вам о ней не расскажет никогда.
Шикарно вообще! Ни единого умножения. Вы — гений. Я вообще вас не правильно сначала понял.
Единственное, надо подумать, а не станет ли d сильно больше k? И не сломает ли это асимптотику? Ведь если для каких-то определенных значений k Ваш алгоритм может сделать сильно больше операций и если это k довольно часто встречается, то все может поломаться.
Кажется, что не должно, ведь разница между простыми до n в среднем log n. Но это в среднем. И судя по Вики эта разница всегда меньше количества простых. Надо только убедится, что так и будет для очень больших простых.
Вот этих комбинаций, реально используемых O(n) и будет. Ровно столько, сколько умножений делает наивный алгоритм.
Я не понимаю, как из размера разности между простыми числами следует, что понадобится меньше умножений. Ведь каждое используемое значение, которое мы предподсчитываем, делается умножением. А нужно нам в каждом внутреннем цикле все те же k, суммарно O(n).
Если вас не затруднит, хотя бы псевдокод вашего решения приведите, пожалуйста.
Я думал k у вас — сколько раз внутренний цикл для данного i выполнится. Туда по определению записано ограничение i*p <= n. А теперь мне кажется, что k у вас количество простых в списке pr для данного i.
Но это все не важно. Суть в том, что то же самое количество значений i*p вам все-равно придется вычислить, ведь это все вычеркнутые по одному разу числа и их надо обязательно вычеркнуть.
Теперь вместо каждого умножения ip вы предлагаете делать prev + i(pr[j]-pr[j-1]), так? Количество умножений не изменилось, потому что мы считаем все те же значения. Сами умножения работают на на ~15% быстрее, потому что один из множителей на треть короче, но на асимптотику это не влияет.
Почему вы количество простых-то берете в степени? все теже итерации сделать предется, все столько-же i*p значений подсчитать. Да, теперь вместо умножения двух чисел в log n бит вы умножаете число в 2/3 log n бит (pr[k]-pr[k-1]) на число в log n бит (i). Все те же n умножений во всем алгоритме, но числа на 33% короче. На асимтотику не влияет.
Была такая мысль, но я так и не придумал, как это сделать быстро.
Ведь для разных i использутеся разный префикс pr. Так что, мы можем много-много итераций не трогать конец списка. А потом должны как-то быстро подсчитать (pr[k]-pr[k-1])*i.
Что бы использовать привычную нотацию вида O(f(n)). Так-то можно обозначить такой буквой, какой мы захотим. Но тут вы правы, я зря Вас запутал этим.
В любом случае, если вы хотите считать битовые операции, то и стандартное решето будет не O(n*log log n), как везде написано, а O(n*log n*log log n), ведь там числа до n складываются.
Ну помилуйте, цикл до 2 миллионов срабатывает мгновенно. На олимпиадах всегда был такой прием — просто считаем операции, вроде присвоения, if-ов и т.д. В секунду таких 400-600 миллионов точно влезет. Тут же выполнится, дай бог 6-8 миллионов. Как раз 1/50-ая
Код и счетчики операций есть в этом комментарии. Никаких оптимизаций почти нет.
Потом, по-моему, вы что-то путаете. То что O(n log log n) работает за 15мс у вас вопросов не вызывает, а в то что O(n) работает за 20мс вы поверить не можете.
Вот только оно не работает, если перед циклом есть какой-то незацикленный отрезок. Еще встает вопрос, а как алгоритм разворота должен остановиться, ведь если цикл есть, то до конца не дойти никак.
Diversity же! Рядом еще есть магическое слово inclusion.
Это получается поредельный случай деления — сразу на N частей =)
На самом деле, тут просто совпало, что можно так по частям сливать от 1 элемента и в итоге получить сложность за n log n.
Потому что можно, например, сливать всегда первые 2 отсортированых списка, что будет n^2.
Но если же сливать 2 самых маленьких всегда, то получается именно схема разделить на 2 части и слить, только развернутая.
Ну, как бы, что бы merge'ить что-то, надо это что-то иметь. Получить его как раз разделением и можно. Слияние — это conquer часть.
А что он тогда по вашему?
Как только вы нашли какой-то элемент в цикле, то достаточно еще 2 раза пройти по списку, чтобы найти весь цикл. Сначала пройдитесь вперед, пока не вернетесь к известному элементу, узнав таким образом длину цикла. Затем пустите 2 указателя с разницей в длину цикла — они встретятся на первом элементе цикла.
Вы про квиксорт, который сортирует на месте в массиве? С разбиением по ведущему элементу? Там не так тривиально это разбиение делается — легко накосячить.
Да это же такой кладезь компромата! Просто представьте, сколько замечательных сюжетов можно пустить по НТВ, а то и по первому каналу, показывая в прайм тайм дикпики оппозиционеров.
А нет ли у вас, случайно, ссылки на этот комментарий?
Ваш пример некорректен. Никто никогда не обещал такой доходности у Теслы. Повезло, совпало — вот и получилась такая доходность. Биткойн вон еще быстрее рос.
Если вы вложили деньги туда где вам обещали 10% плюс-минус, как повезет, а оно собрало 300% годовых — Вам очень повезло. Могло и не повезти. Если вам обещают 300% годовых — точно развод. Вопрос встает, почему бы тогда вместо привлечения Ваших денег тупо не взять кредит под 10%, получить 300% прибыли и заработать 190% самому? Если какая-то достаточно надежно работающая схема есть, то никто Вам о ней не расскажет никогда.
Шикарно вообще! Ни единого умножения. Вы — гений. Я вообще вас не правильно сначала понял.
Единственное, надо подумать, а не станет ли d сильно больше k? И не сломает ли это асимптотику? Ведь если для каких-то определенных значений k Ваш алгоритм может сделать сильно больше операций и если это k довольно часто встречается, то все может поломаться.
Кажется, что не должно, ведь разница между простыми до n в среднем log n. Но это в среднем. И судя по Вики эта разница всегда меньше количества простых. Надо только убедится, что так и будет для очень больших простых.
P.S. жаль, не могу вам плюс в карму поставить!
Вот этих комбинаций, реально используемых O(n) и будет. Ровно столько, сколько умножений делает наивный алгоритм.
Я не понимаю, как из размера разности между простыми числами следует, что понадобится меньше умножений. Ведь каждое используемое значение, которое мы предподсчитываем, делается умножением. А нужно нам в каждом внутреннем цикле все те же k, суммарно O(n).
Если вас не затруднит, хотя бы псевдокод вашего решения приведите, пожалуйста.
Я думал k у вас — сколько раз внутренний цикл для данного i выполнится. Туда по определению записано ограничение i*p <= n. А теперь мне кажется, что k у вас количество простых в списке pr для данного i.
Но это все не важно. Суть в том, что то же самое количество значений i*p вам все-равно придется вычислить, ведь это все вычеркнутые по одному разу числа и их надо обязательно вычеркнуть.
Теперь вместо каждого умножения ip вы предлагаете делать prev + i(pr[j]-pr[j-1]), так? Количество умножений не изменилось, потому что мы считаем все те же значения. Сами умножения работают на на ~15% быстрее, потому что один из множителей на треть короче, но на асимптотику это не влияет.
Почему вы количество простых-то берете в степени? все теже итерации сделать предется, все столько-же i*p значений подсчитать. Да, теперь вместо умножения двух чисел в log n бит вы умножаете число в 2/3 log n бит (pr[k]-pr[k-1]) на число в log n бит (i). Все те же n умножений во всем алгоритме, но числа на 33% короче. На асимтотику не влияет.
Это все-равно 2/3 log n бит. Вы таким образом ускорите умножения, но не ассимптотически.
Была такая мысль, но я так и не придумал, как это сделать быстро.
Ведь для разных i использутеся разный префикс pr. Так что, мы можем много-много итераций не трогать конец списка. А потом должны как-то быстро подсчитать (pr[k]-pr[k-1])*i.
Или я вас не правльно понял?
Да, в этой модели вычислений — вы правы.
Похоже, Вы не туда отвечаете. Смотрите внимательнее, надо нажимать на "Ответить" под комментарием, а не на "Написать комментарий".
Что бы использовать привычную нотацию вида O(f(n)). Так-то можно обозначить такой буквой, какой мы захотим. Но тут вы правы, я зря Вас запутал этим.
В любом случае, если вы хотите считать битовые операции, то и стандартное решето будет не O(n*log log n), как везде написано, а O(n*log n*log log n), ведь там числа до n складываются.
Ну помилуйте, цикл до 2 миллионов срабатывает мгновенно. На олимпиадах всегда был такой прием — просто считаем операции, вроде присвоения, if-ов и т.д. В секунду таких 400-600 миллионов точно влезет. Тут же выполнится, дай бог 6-8 миллионов. Как раз 1/50-ая
Код и счетчики операций есть в этом комментарии. Никаких оптимизаций почти нет.
Потом, по-моему, вы что-то путаете. То что O(n log log n) работает за 15мс у вас вопросов не вызывает, а в то что O(n) работает за 20мс вы поверить не можете.