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

Любители посоревноваться в алгоритмах часто говорят об асимптотике того или иного решения задачи. При этом нередко можно встретить высказывания, что, мол, «вот этот» алгоритм работает за 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» в том же тесте по ссылке выше). Даже в тех случаях, когда скорость обоих методом примерно равная, глубина рекурсии уменьшается.

Вывод

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