На одной асимптотике далеко не уедешь…


При выборе алгоритма часто говорят об асимптотике того или иного решения задачи. При этом можно встретить высказывания, что, мол, «вот этот» алгоритм работает за O(n), а «вон тот» – за O(n·log(n)), значит первый однозначно лучше. Либо раз оба метода работают за O(n²), значит их можно считать равнозначными, и обсуждать, чем один может быть лучше другого, большого смысла нет.


Лично я не могу согласиться с таким мнением, по крайней мере, когда речь идёт в контексте программирования, поэтому решил написать данную статью и поделиться некоторыми мыслями о возможных нюансах.


Как вам такое?


  1. Не стоит забывать, что операции, которые можно принять за O(1), бывают очень простые (сложение/вычитание), а бывают весьма навороченные (многоэтажные формулы со сложными функциями). Операции деления, вычисления тригонометрических и логарифмических функций, степеней (включая корни) и т.п., особенно с вещественными числами, выполняются в разы (а иногда в десятки и сотни раз медленнее), чем операции сложения, вычитания и умножения, особенно с целыми числами. Таким образом, даже O(1) в разных алгоритмах могут отличаться на порядки.
  2. Даже если сложность операций примерно одинакова и их количество, на первый взгляд, примерно то же, реальное число операций может существенно различаться. К примеру, один алгоритм проходит по всему массиву, другой – лишь по его части (которая формально может быть любой длины, однако на практике довольно коротка, скажем, 1/10 от длины массива). А если такое происходит ещё и во вложенном цикле, то мы получим реальную разницу в скорости в 100 раз. Кроме того, если вы помните, константы при определении асимптотической сложности, не учитываются. Т.е. даже если вы обернёте ваш алгоритм в цикл на 1 млн итераций, то ваше «O» не изменится, по факту же скорость упадёт примерно на 6 десятичных порядков. На практике такое, конечно, вряд ли можно встретить, но алгоритмов, в которых проход по одному и тому же массиву осуществляется несколько раз (либо происходит несколько операций сортировки, повторяющиеся вложенные циклы и пр.), предостаточно. Да и, скажем, log(n) может означать как log2(n), так и log10(n), разница между которыми примерно в 3.32 раза.
  3. Не забывайте, что кроме скорости есть и другие важные параметры, например, объём используемой памяти. Поэтому алгоритм, работающий за O(n²) в отдельных случаях может быть более предпочтительным, чем алгоритм, работающий за O(n) или O(n·log(n)), но использующий значительный объём памяти. Количество используемых элементов памяти также может оцениваться с помощью «O», и при оценке сложности алгоритма неплохо бы писать рядом и оценку использования памяти.
  4. Некоторые из алгоритмов могут потребовать предварительной подготовки (и, опять же, памяти), а некоторые – нет. Хороший пример – тест простоты числа. Его можно реализовать множеством способов, но рассмотрим и сравним лишь 2 из них: метод перебора (сложностью около O(sqrt(n)) операций деления) и с помощью решета Эратосфена или Аткина (тест простоты выполняется за O(1), но с предварительной подготовкой массива порядка O(n·log(log(n))) или O(n/log(log(n))) соответственно). Использование памяти для последнего алгоритма можно соптимизировать как минимум до 32 мегабайта на 1 млрд чисел (т.е. до 1 байта на 30 чисел), причём эти значения можно даже не вычислять при каждом запуске программы, а закэшировать, сохранив на диске. Какой из способов предпочесть – сильно зависит от конкретного случая использования, иногда гораздо более предпочтительным окажется тест Миллера или Миллера-Рабина. Кстати, тест простоты методом перебора – неплохой пример того, что в зависимости от исходного значения (n) работа алгоритма может завершиться как на первых итерациях (чётное число или число, кратное 3, 5, 7), так и выполняться довольно приличное время (большое простое число), хотя формально его сложность, как я уже говорил, составляет O(sqrt(n)). Кому интересно, вот «здесь» я приводил простые методы алгоритмического ускорения теста простоты только лишь для одного метода перебора с реализацией на C++. А вот «здесь» есть пример реализации метода Миллера на Python.
  5. Важен не только сам алгоритм, но и его реализация. Один и тот же алгоритм может различаться по скорости в сотни раз просто из-за выбора разных языков программирования. Алгоритм, работающий, скажем, за O(n·log(n)) на C/C++ может оказаться ощутимо быстрее, чем работающий за O(n) на Python, причём для довольно больших n. Кроме того, есть множество нюансов оптимизации, применительно к платформе, формату хранения данных, ветвлению, реализации функций стандартных библиотек и пр. К примеру, если один алгоритм позволяет оптимизировать работу с кэшем процессора, использовать SIMD или многопоточную работу, а другой – нет, скорость может отличаться в разы или даже в десятки раз (при том, что всё остальное примерно одинаково). Последовательная работа с массивом, расположенным в памяти единым блоком, только лишь из-за специфики его организации быстрее, чем со связным списком (разумеется, если не рассматривать вставку элементов в начало или в середину массива/списка). Кэширование данных, полученных на предыдущих итерациях (например, в рекурсивных алгоритмах) могут увеличить скорость на много порядков. И т.д. Кто-то ехидно воскликнет: «К чему это всё? Мы же обсуждаем сами алгоритмы, а не их реализацию!» К тому, что некоторые алгоритмы позволяют без труда реализовать хорошую оптимизацию, иные же усложняют этот процесс или даже делают какую-то оптимизацию невозможной. Я не призываю к преждевременной оптимизации, однако не зря же специалисты по высокопроизводительным системам говорят: «При написании таких систем, над производительностью системы приходится думать уже на этапе архитектуры и дизайна системы, еще до того, как написана хоть одна строчка кода» (цитата из статьи по ссылке выше).

Если подумать ещё, наверняка можно найти и другие нюансы, но по-моему, и этого уже достаточно, чтобы хорошенько задуматься: действительно ли «O» – единственный важный показатель скорости алгоритма?


Неужели разница в скорости в 2, 5, 10 раз ничего не значит? Почему же большинство людей предпочитают быстрые SSD, нежели медленные HDD? Ведь алгоритмы копирования везде одинаковые (по крайней мере, лично я больше чем O(n) пока не встречал) :)


А представьте, какова может быть разница, если просуммировать все эти нюансы! Некоторые алгоритмы с бóльшим «O» могут работать чуть быстрее, чем иные с меньшим «O» (по меньшей мере, для относительно небольших n… кстати, а всегда ли n должно стремиться к бесконечности при оценке скорости алгоритма?)


Практический пример


В качестве конкретного примера приведу методы сортировки массивов. Многие думают, что методы сортировки пузырьком и вставками примерно одинаковы по скорости (поскольку сложность обоих составляет O(n²)). Однако я не раз убеждался на практике, что сортировка вставками работает почти на порядок быстрее. Для иллюстрации этого некоторое время назад я сделал небольшой сравнительный тест нескольких методов сортировки (ниже в комментариях выложены результаты теста на моём компьютере, соотношение скорости сортировки пузырьком и вставками указано в строке «Bubble/insertion sort time ratio»).


Кроме того, алгоритм быстрой сортировки (который тоже имеет множество реализаций, ощутимо различающихся как по скорости, так и по глубине рекурсии) может модифицироваться таким образом, что при достижении некоторого порога размера массивов, на которые происходит деление исходного массива (например, когда элементов становится меньше 16-ти; а иногда ещё и при достижении определённой глубины рекурсии), сортировка переключается на… сортировку вставками (либо дальнейшая быстрая сортировка прекращается, а сортировка вставками применяется уже позже ко всему не до конца отсортированному массиву). Казалось бы, зачем это делается, ведь сортировка вставками значительно медленнее быстрой сортировки? Однако на практике оказывается, что сортировка небольших массивов зачастую происходит чуть быстрее именно «вставками», нежели «быстрым» методом («quick/quick-insertion sort time ratio» в том же тесте по ссылке выше). Даже в тех случаях, когда скорость обоих методом примерно равная, глубина рекурсии уменьшается.


Вывод


Какой вывод можно сделать из всего этого? Очень простой: теория – это хорошо, но она должна подкрепляться практикой и знаниями возможных подводных камней. Как гласит японская пословица, знание является наградой за действие.


Эпилог


Хочу поблагодарить читателей за проявленный интерес к статье, особенно тех, кто поделился своими мыслями в комментариях. Это моя первая статья на Хабре, и для меня это ценно. Именно после прочтения ваших сообщений я решил добавить этот эпилог.


Разумеется, при бесконечно больших объёмах данных (n → ∞) асимптотическая оценка сложности будет как нельзя лучше отражать характер роста времени работы алгоритмов. И никакие доводы, что "сложение быстрее деления" или что "константа всё же имеет значение" не будут столь важны, как эта оценка. Однако в реальной жизни не все так идеально, как в математике, и объём данных почти всегда ограничен (причём, нередко довольно небольшими величинами). А это значит, что есть смысл брать во внимание и другие параметры и оценить реальную эффективность с учётом этих параметров и возможных диапазонов величины n. Но и здесь важно трезво смотреть на ситуацию: не вырастет ли "завтра" это n на порядок, к примеру, в связи с технологическим ростом или ростом бизнеса? Может быть, действительно есть смысл использовать алгоритм, который сейчас работает в 1.5 раза медленнее, но через месяц окажется в 2 раза быстрее, а через год – в 5? Или даже сделать 2 алгоритма и динамически выбирать между ними в зависимости от объёма входных данных! По этому поводу мне вспомнилась история с катастрофой на Ariane 5.


Вряд ли будет открытием, что к любому делу нужно подходить с умом. Асимптотика придумана умными людьми, и она важна. Провести замер скорости без учёта асимптотики будет тоже не очень разумно. Но чтобы "уехать далеко", лучше иметь два колеса, а не одно. А ещё лучше – четыре. Нужно учитывать сразу несколько параметров. И помнить о приоритетах. Где-то наиболее важным будет скорость работы алгоритма, где-то объём используемой памяти, где-то это всё будет вообще несущественным (ввиду малых значений), а гораздо важнее написать функцию быстро. И т.д.


Ключевые идеи статьи:


  1. Если вам важна скорость, то при выборе алгоритма с одинаковой асимптотикой (скорости работы и объёма требуемой памяти) обращайте внимание на другие характеристики, которые могут существенно влиять на скорость (различаясь в разы или даже порядки) и проводите тесты. В некоторых случаях довольно похожие алгоритмы с одинаковой сложностью и схожими операциями, как в моём примере про сортировку пузырьком и вставками, могут существенно отличаются по скорости (кстати, вот ссылка на ещё один тест алгоритмов сортировки, уже не мой).
  2. Небольшие отличия в оценке асимптотической сложности могут перекрываться другими нюансами (в т.ч. описанными выше). К примеру, логарифм часто можно принять за константу (поскольку, к примеру, log2(1'048'576) = 20, а log2(1'073'741'824) = 30), поэтому в случае O(n) и O(n·log(n)) есть смысл сравнить реальную эффективность алгоритмов даже при значительных n. Если же оценка существенна: O(n) и O(n²), то первый алгоритм, разумеется, почти всегда будет быстрее уже при довольно незначительном объёме входных данных.
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 37

    +2
    youtu.be/FJJTYQYB1JQ
    Это должно быть здесь. Доклад Андрея Александреску про алгоритмическую сложность и реальность на CppCon 2019.
      0
      for(;;) goto это мощно!
      +7
      Если простыми словами:
      Лично я на это не смотрю как показатель скорости алгоритма. Это всего лишь примерная оценка, что бы понять как алгоритм будет себя вести при увеличение данных в 10, 100, 1000 раз.

      Так же надо не забывать, что есть ещё константа, которая может быть достаточно высокой, что на маленьком количестве входных данных линейный алгоритм будет медленнее квадратного.
      Но если входных данных будет на несколько порядков больше, то высокая константа будет не так страшна и линейный победит.
        0
        Абсолютно согласен, именно как примерная оценка применительно к объёму исходных данных. Плюс оценивать другие параметры (константы, сложность операций, используемую память и прочее).

        Конечно, если вы работаете с миллионными массивами, то сравнивать алгоритмы O(n) и O(n²), пожалуй, нет смысла, но в целом финальную скорость лучше, конечно, оценивать на практике, потому как даже log2(1048576) = 20 всего лишь :)
          0
          по определению нотация big O используется для оценки при очень больших числах и числах стремящихся к бесконечности. Вы же говорите, что она не работает на маленьких числах и не учитывает константы. Вот это открытие, с учетом того, что она и не должна по определению. Проще статью на википедии прочитать и там это написано в первой же строчке: en.wikipedia.org/wiki/Big_O_notation
            0
            Иногда через «O» оценивают скорость вне зависимости от размера n.
            Если вы так не делаете, тогда отлично, значит для вас мои речи не столь актуальны.

            Тем не менее, что считать «большими числами»? Миллиард – это много? Однако ж log2(1млрд) ≈ 30. Не такой уж и большой коэффициент в некоторых случаях. Я уже начинаю повторяться :))
        +1

        Ещё нужно учитывать характер входных данных, которые будут использоваться на практике. Например, по логике их требуется сначала отсортировать за какое-то O(), но по факту они всегда приходят почти отсортированными, надо только пару элементов подвинуть.


        Я вообще не думаю про O(), пока не получу первый код и не испытаю его на правильном наборе данных. Код решает практические задачи, а как он себя ведёт на N, стремящемся в бесконечность, вопрос чисто теоретический. На практике бесконечности не существует.

          +3

          И правильно, чего про O() думать? Все базовые алгоритмы описаны (и реализованы в либах), в большинстве случаев выбор подходящего по этой характеристике – как руки перед едой помыть, умственных усилий не требует.


          Хотя, конечно, бывают и ошибки с этим.

            +1
            1: В описаниях алгоритмов часто используются абстрактные структуры данных, например какой-нибудь идеальный список в вакууме: добавьте элемент в список, удалите из списка, возьмите из списка минимальный элемент. А что лучше, постоянно искать минимальный элемент или просто хранить «список» всегда отсортированным? В зависимости от твоей интерпретации и реализации скорость может отличаться в десятки раз.
            2: Авторам описанного и особенно реализованного по барабану, в каком виде у тебя исходные данные. Например, хранить граф или 3-мерную сетку можно десятком способов, удобных для одних целей и неудобных для других. Как ты будешь конвертировать свои конкретные данные в удобный алгоритму/его реализации формат и сколько времени это займёт, никого не интересует.
            3: Имеющиеся реализации довольно часто ставят себе целью просто решить задачу, а не решить задачу эффективно или хотя бы аккуратно. Последний пример: искал триангуляцию полигонов для .NET. В реализации популярной библиотеки Poly2Tri элементарная сущность «вершина» описана ссылочным типом. И никак его не заменить на value-тип, не переписывая 2/3 библиотеки. Просто отлично ― больше мусора богу мусора.
              0

              1: Вообще-то в описании алгоритма в таком случае обычно будет написано "будем хранить данные в двоичной куче".
              2-3: обычно пролетим по скорости, но как правило на ту самую константу, а не до уровня O(n²) вместо O(n) на ровном месте. Т.е. думать об оптимизации всё равно придётся (после поиска узких мест, конечно – всё остальное надо оптимизировать на простоту и понятность кода)

          +1
          О модификация алгоритма быстрой сортировки что-то было у Кормена: e-maxx.ru/bookz/files/cormen.pdf, стр. 168, упражнение 8.4-4. Это наверное немного не то, о чем Вы говорите, но суть в том, что в этом случае нужно просто правильно посчитать асимптотику.
          Но в целом Вашу риторику одобряю.
            0
            Хм, до такого варианта я не додумался, и мне он кажется даже более правильным. Хотя суть та же.
            Спасибо за ссылку! Добавлю такую ремарку в статью…
            0

            Вывод вроде как противоположный тому, что в заголовке. Асимптотика хороша, когда ехать далеко, а при перемещении на близкие расстояния достаточно велосипеда.

              +3

              Я к этому так отношусь. Что будет на маленьких данных обычно не важно. Если внезапные проблемы возникают, то они обычно возникают на больших данных. А там уже работает та самая асимптотика.


              Ещё логарифм при таком подходе можно смело заменять константой и вычёркивать из асимптотики. А вот квадрат уже не вычеркнешь.


              В общем такой очень невдумчивый подход это стараться избегать квадратичной сложности, если есть возможность. Всё, что не квадратичное, скорей всего будет работать приемлемо. Квадратичная может "выстрелить" в самый неподходящий момент и положить всё на лопатки. Не-квадратичная если и выстрелит, то деградация системы будет понятна и пропорциональна размеру входа и обычно с этим можно жить.


              Конечно там, где известно, что данных будет много или участок кода "горячий", желательно вдумчиво работать с самого начала.

                0

                Не только квадратичная, но и линейная может выстрельнуть, т.е. нужно снижать линейную до константной (поиск в массиве -> извлечение из словаря). Может сверху где-то и вылезает N * M или квадраты, но пофиксить представляется возможным только внизу.


                Кстати, на тему случайной квадратичности даже сайт есть: https://accidentallyquadratic.tumblr.com/

                  0

                  Заполнение словаря в динамике будет линейным в лучшем случае. Навскидку если только в ПЗУ прошить

                +12
                Как вам такое?
                Да никак, в принципе. Нотация O-большое показывает исключительно характер роста времени выполнения при неограниченном росте выбранных переменных. Больше ничего. И для потребления памяти такая нотация тоже существует.

                Может для кого-то это и не очевидно из-за изначально неправильного понимания, но никакого вскрытия покровов теории и противоречия с ней тут нет.

                действительно ли «O»  –  главный показатель скорости алгоритма?
                Если один алгоритм выигрывает у другого асимптотически, то, грубо говоря, это значит, что всегда найдётся такой объём входных данных, начиная с которого асимптотически выигрышный алгоритм выполняется быстрее. В отдельных случаях, когда практические объёмы невелики, использование алгоритма с лучшей асимптотикой может быть не выгодно. Но общая закономерность такова, и она не зависит от реальных коэффициентов. По этой причине действительно оценка О-большое является главным показателем скорости алгоритма. Никто никогда нигде не утверждал, что она является достаточной для сравнения времени работы всех частных случаев.
                  +1
                  Абсолютно согласен! Не следует оценке вычислительной сложности придавать больше смысла, чем она подразумевает.
                    0
                    Нотация O-большое показывает исключительно характер роста времени выполнения при неограниченном росте выбранных переменных
                    Это (выделенное) ключевой момент, пожалуй. Но в жизни такого не бывает (практически) :)

                    Если один алгоритм выигрывает у другого асимптотически, то, грубо говоря, это значит, что всегда найдётся такой объём входных данных, начиная с которого асимптотически выигрышный алгоритм выполняется быстрее.
                    Любой алгоритм важен не сам по себе, а применительно к какому-то случаю с данным, имеющими определённый характер (тип, объём, разброс значений и т.д). Не всегда та самая величина, при которой начинается выигрыш, достигается. Собственно, как вы и сами написали:
                    В отдельных случаях, когда практические объёмы невелики, использование алгоритма с лучшей асимптотикой может быть не выгодно.
                      –2
                      Плюсую. В качестве примера могу указать умножение по методу Карацубы.
                        0

                        А с ним-то что не так?

                          0
                          Проигрывает он по времени школьному столбику при коротких операндах
                    +4
                    Я бы назвал статью наоборот, «на одном замере далеко не уедешь». Часто «эффективные менеджеры» или юные программисты, замеряют алгоритм на начальных и похожих данных и отправляют в прод. Не разобравшись, что алгоритм растет вмест O(n log n) по O (n ^ 2).
                    И в начале, никто ничего не замечает, зато через полгода-год, если бизнес растет, то проблемы вырастают внушительные и разбираться в 100К строчках кода, в поисках, что же не так в спешке бывает мучительно больно.
                      0
                      Хорошее замечание про рост бизнеса.
                      Однако ехать на одном колесе всегда не очень удобно. Хоть на переднем, хоть на заднем. Лучше на обоих (а ещё лучше – на 4-х).
                      Как вариант, в случаях, когда объём данных может сильно меняться (что не всегда, конечно, удаётся предусмотреть заранее), и скорость действительно важна, можно динамически выбирать более эффективный алгоритм.
                      0
                      или в середину массива/списка

                      Но ведь эту середину ещё найти надо, так что (по моему опыту) даже вставлять/удалять в середину массива выгоднее. Особенно если это, например, массив тривиально двигаемых интов.

                        +4

                        Вы сравниваете немного разные характеристики. Особенно в пунктах про память и количество тактов на операцию сложения или деления.


                        Несколько моментов:


                        • есть три функции сложности алгоритма (в плане и памяти и количества операций): big-Oh (O), big-omega (Ω), big-theta (Θ); O(f(n)) — верхняя граница (характеристика), Ω(f(n)) — нижняя граница, Θ(f(n)) — строгое "равно"


                        • все три характеристики определяют порядок роста характеристики (потребление памяти либо количество операций); в университете нам объяснили это в плане математической основы: считайте что алгоритм принимает на вход бесконечно большой (ну или просто крайне большой) объем данных; в таком случае какая разница сколько тактов будет выполняться деление, если оно будет выполнено n^2, где n ~= 10^20? зато в сравнении с алгоритмом где будет выполнено n операций деления, где n ~= 10^20 — мы говорим о довольно-таки приличном различии


                        • нужно различать (по крайней мере на собеседованиях в фейсбук и гугл) время выполнения и алгоритмическую сложность алгоритма; в первом случае вы считаете грубое количество операций, во втором — порядок роста этого количества операций


                        • ну и не нужно забывать, что сравнение порядка роста количества операций и порядка роста использования памяти — две разные характеристики алгоритма, и часто на тех же собеседованиях в гуглы-фейсбуки вас попросят (может и неявно) принять решение о ускорении алгоритма благодаря большему потреблению памяти либо сокращению количества выполняемых операций (при этом скорее всего может идти речь попросту о разных структурах данных)


                          0
                          Не бывает бесконечно большого кол-ва данных. Бывает конкретный случай применения алгоритма. И если этот случай предполагает рост в будущем, тогда можно говорить о том, при каком n стоит перейти на другой алгоритм.

                          К примеру, при бесконечно большом n сортировка подсчётом для дискретных данных – наилучший алгоритм сортировки. Однако в жизни зачастую n оказывается гораздо меньше возможной величины разброса данных, и этот алгоритм, соответственно, становится не самым лучшим выбором. Даже если не брать во внимание кол-во используемой им памяти.

                          По большому счёту, статья скорее не о сравнении O(n) и O(n²) для больших n, а о сравнении O(n) и O(n) или O(n²) и O(n²), как в примере с сортировкой пузырьком и вставками. И о сравнении O(n) и O(n·log(n)) при относительно умеренных n. Логарифм в этом случае действительно можно считать константой :)

                          Вы сравниваете немного разные характеристики.
                          Я их не сравниваю, а говорю, что они тоже имеют место быть и тоже влияют на эффективность алгоритма.
                            –1
                            К примеру, при бесконечно большом n сортировка подсчётом для дискретных данных – наилучший алгоритм сортировки

                            Простите?


                            Так и быть, поддамся… Насколько я понимаю, сортировка подсчетом имеет сложность O(n) и по времени, и по памяти. Тот же mergesort даст O(log(n)). А теперь сравните n ?= log(n) — даже для чисел больше 2 вы получаете заметную разницу.


                            Не бывает бесконечно большого кол-ва данных. Бывает конкретный случай применения алгоритма

                            Ну вот вы опять сравниваете рантайм со сложностью. Конкретику с математической моделью.


                            Асимптотику используют для сравнения алгоритмов, а не конкретных реализаций на конкретных данных.


                            Я их не сравниваю, а говорю, что они тоже имеют место быть

                            Таким образом, даже O(1) в разных алгоритмах могут отличаться на порядки.

                            Судите сами.


                            Кстати, по этому же параграфу: никто не считает сложные функции как одну операцию, смело заявляя об О(1). Для оценки сложности сложных алгоритмов используется немного другой подход (выбирается наиболее быстро возрастающая функция из всех функций сложности каждой части алгоритма; иными словами — самая сложная часть и будет сложностью всего алгоритма). А вы считаете такты. Но какая разница сколько тактов выполняется пара умножений в умножении матриц, пусть даже их размерность — тысячи на тысячи, если алгоритм будет при этом множить их десятки раз?


                            О(1) значит всегда то же, для любых алгоритмов, реализованных на любых ЯПах и выполненных на любых машинах. Хотите считать рантайм (как в вашем высказывании о сложности деления против сложения) — учитывайте и процессор(-ы), на которых эти операции выполняются (не только микрооптимизации процессорные, но и компиляторные — SIMD и прочие изголения в зависимости от целевой платформы).

                              0
                              Тот же mergesort даст O(log(n)).
                              Как вы представляете себе какую-либо сортировку со сложностью меньше, чем 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 раза. Хотя операции примерно одинаковы, сложность одинакова, да и технически они имеют сходства похожи. И вряд ли на каком-либо процессоре будет иначе.
                                0
                                Тот же mergesort даст O(log(n)).

                                Вот что я забыл поправить перед отправкой с телефона


                                сортировка вставками против сортировки пузырьком

                                В том и суть асимптотической нотации — никто не будет выбирать между двумя алгоритмами O(n^2) — это бессмысленно, как ни посмотри. Сравнивать будут в сторону O(log(n)) и O(n).

                                  0
                                  Если есть вариант с O(n), O(log(n)) или O(n·log(n)), то безусловно.
                                  0
                                  Как вы представляете себе какую-либо сортировку со сложностью меньше, чем O(n)?

                                  Меньше, чем O(nlogn), на самом деле. Можно формально показать, что сортировки сравнениями, работающей быстрее, чем эта оценка, быть не может.

                                    0
                                    Есть же сортировки не только сравнением.
                                    Counting Sort и Radix Sort при небольшом разбросе значений можно принять за O(n).
                                    Bucket Sort в некоторых случаях с некоторыми оговорками – тоже O(n).
                            +1
                            Да и, скажем, log(n) может означать как log2(n), так и log10(n), разница между которыми примерно в 3.32 раза.

                            Обычно это log2. (Бинарные деренья, бинарный поиск)

                              0
                              Согласен, но всегда бывают исключения.
                              0

                              К слову про сортировки. На случайных данных быстрая сортировка дает на 30% больше сравнений, чем сортировка слиянием, хотя асимптотика в среднем случае у обоих O(n*log(n)). Но при этом влияет природа данных — для массива строк быстрее будет сортировка слиянием, так как сравнение занимает значительное время, а для массива целых чисел быстрее будет быстрая сортировка, за счет того, что обращение к данным идет последовательно, и кэширование в процессоре работает лучше.

                                0
                                А иногда быстрее бывает RadixSort (пример) :)

                              Only users with full accounts can post comments. Log in, please.