Иногда через «O» оценивают скорость вне зависимости от размера n.
Если вы так не делаете, тогда отлично, значит для вас мои речи не столь актуальны.
Тем не менее, что считать «большими числами»? Миллиард – это много? Однако ж log2(1млрд) ≈ 30. Не такой уж и большой коэффициент в некоторых случаях. Я уже начинаю повторяться :))
Как вы представляете себе какую-либо сортировку со сложностью меньше, чем O(n)? MergeSort имеет сложность O(n·log(n)).
Асимптотику используют для сравнения алгоритмов, а не конкретных реализаций на конкретных данных.
Я с этим и не спорю :)
Однако если в алгоритме «А» 30 циклов сложностью O(n) каждый, а в алгоритме «Б» – один сложностью O(n·log(n)), то «А» будет быстрее лишь при n > 2^30 (≈ 1 млдр). Даже без учёта реализаций. При бесконечном объёме данных (т.е. в нереальном случае) «А», конечно, когда-нибудь победит.
Да и основная моя мысль – это рассмотрение алгоритма с практической точки зрения, где сложность – не единственный важный показатель. К тому же, алгоритм тоже определяет реализацию. Если вам нужно делить, вы никак не сделаете это так же быстро, как сложение. Какой смысл рассматривать эффективность алгоритма вообще без какой-либо привязки к возможной реализации?
Судите сами.
Я не вижу противоречия. Возможно, мы говорим о разных вещах, имея в виду фразу «разные характеристики» :)
никто не считает сложные функции как одну операцию, смело заявляя об О(1)
Смотря какие. Факториал – да, не считают. А сложение или деление обычно считают.
Но какая разница сколько тактов выполняется пара умножений в умножении матриц, пусть даже их размерность — тысячи на тысячи, если алгоритм будет при этом множить их десятки раз?
Не понимаю, что вы хотите сказать. Разве не тем важнее скорость каждой операции, чем больше их кол-во?
Хотите считать рантайм (как в вашем высказывании о сложности деления против сложения) — учитывайте и процессор(-ы), на которых эти операции выполняются
В идеале, конечно, и это стоило бы учесть, но предусмотреть такое гораздо сложнее (разве что опробовать на desktop и mobile, к примеру). Учитывайте максимум из того, что можете. Понятное дело, что преимущество на 10% на одной системе может оказаться потерей на других. Но если разница в несколько раз…
Смотрите, мы можем ещё долго рассуждать и спорить о каких-то деталях, но суть статьи я дописал сегодня в разделе «Эпилог», а наглядный пример – это сортировка вставками против сортировки пузырьком. Обе эти сортировки везде обозначаются как O(n²), но на деле отличаются по скорости в разы. В моём тесте – в 7-10 раз, вот "здесь" – в 3 раза. Хотя операции примерно одинаковы, сложность одинакова, да и технически они имеют сходства похожи. И вряд ли на каком-либо процессоре будет иначе.
Не бывает бесконечно большого кол-ва данных. Бывает конкретный случай применения алгоритма. И если этот случай предполагает рост в будущем, тогда можно говорить о том, при каком n стоит перейти на другой алгоритм.
К примеру, при бесконечно большом n сортировка подсчётом для дискретных данных – наилучший алгоритм сортировки. Однако в жизни зачастую n оказывается гораздо меньше возможной величины разброса данных, и этот алгоритм, соответственно, становится не самым лучшим выбором. Даже если не брать во внимание кол-во используемой им памяти.
По большому счёту, статья скорее не о сравнении O(n) и O(n²) для больших n, а о сравнении O(n) и O(n) или O(n²) и O(n²), как в примере с сортировкой пузырьком и вставками. И о сравнении O(n) и O(n·log(n)) при относительно умеренных n. Логарифм в этом случае действительно можно считать константой :)
Вы сравниваете немного разные характеристики.
Я их не сравниваю, а говорю, что они тоже имеют место быть и тоже влияют на эффективность алгоритма.
Хорошее замечание про рост бизнеса.
Однако ехать на одном колесе всегда не очень удобно. Хоть на переднем, хоть на заднем. Лучше на обоих (а ещё лучше – на 4-х).
Как вариант, в случаях, когда объём данных может сильно меняться (что не всегда, конечно, удаётся предусмотреть заранее), и скорость действительно важна, можно динамически выбирать более эффективный алгоритм.
Нотация O-большое показывает исключительно характер роста времени выполнения при неограниченном росте выбранных переменных
Это (выделенное) ключевой момент, пожалуй. Но в жизни такого не бывает (практически) :)
Если один алгоритм выигрывает у другого асимптотически, то, грубо говоря, это значит, что всегда найдётся такой объём входных данных, начиная с которого асимптотически выигрышный алгоритм выполняется быстрее.
Любой алгоритм важен не сам по себе, а применительно к какому-то случаю с данным, имеющими определённый характер (тип, объём, разброс значений и т.д). Не всегда та самая величина, при которой начинается выигрыш, достигается. Собственно, как вы и сами написали:
В отдельных случаях, когда практические объёмы невелики, использование алгоритма с лучшей асимптотикой может быть не выгодно.
Абсолютно согласен, именно как примерная оценка применительно к объёму исходных данных. Плюс оценивать другие параметры (константы, сложность операций, используемую память и прочее).
Конечно, если вы работаете с миллионными массивами, то сравнивать алгоритмы O(n) и O(n²), пожалуй, нет смысла, но в целом финальную скорость лучше, конечно, оценивать на практике, потому как даже log2(1048576) = 20 всего лишь :)
Если вы так не делаете, тогда отлично, значит для вас мои речи не столь актуальны.
Тем не менее, что считать «большими числами»? Миллиард – это много? Однако ж log2(1млрд) ≈ 30. Не такой уж и большой коэффициент в некоторых случаях. Я уже начинаю повторяться :))
Я с этим и не спорю :)
Однако если в алгоритме «А» 30 циклов сложностью O(n) каждый, а в алгоритме «Б» – один сложностью O(n·log(n)), то «А» будет быстрее лишь при n > 2^30 (≈ 1 млдр). Даже без учёта реализаций. При бесконечном объёме данных (т.е. в нереальном случае) «А», конечно, когда-нибудь победит.
Да и основная моя мысль – это рассмотрение алгоритма с практической точки зрения, где сложность – не единственный важный показатель. К тому же, алгоритм тоже определяет реализацию. Если вам нужно делить, вы никак не сделаете это так же быстро, как сложение. Какой смысл рассматривать эффективность алгоритма вообще без какой-либо привязки к возможной реализации?
Я не вижу противоречия. Возможно, мы говорим о разных вещах, имея в виду фразу «разные характеристики» :)
Смотря какие. Факториал – да, не считают. А сложение или деление обычно считают.
Не понимаю, что вы хотите сказать. Разве не тем важнее скорость каждой операции, чем больше их кол-во?
В идеале, конечно, и это стоило бы учесть, но предусмотреть такое гораздо сложнее (разве что опробовать на desktop и mobile, к примеру). Учитывайте максимум из того, что можете. Понятное дело, что преимущество на 10% на одной системе может оказаться потерей на других. Но если разница в несколько раз…
Смотрите, мы можем ещё долго рассуждать и спорить о каких-то деталях, но суть статьи я дописал сегодня в разделе «Эпилог», а наглядный пример – это сортировка вставками против сортировки пузырьком. Обе эти сортировки везде обозначаются как O(n²), но на деле отличаются по скорости в разы. В моём тесте – в 7-10 раз, вот "здесь" – в 3 раза. Хотя операции примерно одинаковы, сложность одинакова, да и технически они имеют сходства похожи. И вряд ли на каком-либо процессоре будет иначе.
К примеру, при бесконечно большом n сортировка подсчётом для дискретных данных – наилучший алгоритм сортировки. Однако в жизни зачастую n оказывается гораздо меньше возможной величины разброса данных, и этот алгоритм, соответственно, становится не самым лучшим выбором. Даже если не брать во внимание кол-во используемой им памяти.
По большому счёту, статья скорее не о сравнении O(n) и O(n²) для больших n, а о сравнении O(n) и O(n) или O(n²) и O(n²), как в примере с сортировкой пузырьком и вставками. И о сравнении O(n) и O(n·log(n)) при относительно умеренных n. Логарифм в этом случае действительно можно считать константой :)
Я их не сравниваю, а говорю, что они тоже имеют место быть и тоже влияют на эффективность алгоритма.
Однако ехать на одном колесе всегда не очень удобно. Хоть на переднем, хоть на заднем. Лучше на обоих (а ещё лучше – на 4-х).
Как вариант, в случаях, когда объём данных может сильно меняться (что не всегда, конечно, удаётся предусмотреть заранее), и скорость действительно важна, можно динамически выбирать более эффективный алгоритм.
Любой алгоритм важен не сам по себе, а применительно к какому-то случаю с данным, имеющими определённый характер (тип, объём, разброс значений и т.д). Не всегда та самая величина, при которой начинается выигрыш, достигается. Собственно, как вы и сами написали:
Спасибо за ссылку! Добавлю такую ремарку в статью…
Конечно, если вы работаете с миллионными массивами, то сравнивать алгоритмы O(n) и O(n²), пожалуй, нет смысла, но в целом финальную скорость лучше, конечно, оценивать на практике, потому как даже log2(1048576) = 20 всего лишь :)