- PVSM.RU - https://www.pvsm.ru -
Любители посоревноваться в алгоритмах часто говорят об асимптотике того или иного решения задачи. При этом нередко можно встретить высказывания, что, мол, «вот этот» алгоритм работает за O(n), а «вон тот» – за O(n·log(n)), значит первый однозначно быстрее и, следовательно, лучше. Либо раз оба метода работают за O(n²), значит их можно считать равнозначными, и обсуждать, чем один может быть лучше другого, особого смысла нет.
Лично мне такое
Если подумать ещё, наверняка можно найти и другие нюансы, но по-моему, и этого уже достаточно, чтобы хорошенько задуматься: действительно ли «O» – главный показатель скорости алгоритма?
Неужели разница в скорости в 2, 5, 10 раз ничего не значит? Почему же большинство людей предпочитают быстрые SSD, нежели медленные HDD? Ведь алгоритмы копирования везде одинаковые (по крайней мере, лично я больше чем O(n) пока не встречал) :)
А представьте, какова может быть разница, если просуммировать все эти нюансы! Некоторые алгоритмы с бóльшим «O» могут работать чуть быстрее, чем иные с меньшим «O» (по меньшей мере, для относительно небольших n… кстати, а всегда ли n должно стремиться к бесконечности при оценке скорости алгоритма?)
В качестве конкретного примера приведу методы сортировки массивов. Многие думают, что методы сортировки пузырьком [10] и вставками [11] примерно одинаковы по скорости (поскольку сложность обоих составляет O(n²)). Однако я ни раз убеждался на практике, что сортировка вставками работает почти на порядок быстрее. Для иллюстрации этого некоторое время назад я сделал небольшой сравнительный тест нескольких методов сортировки [12] (ниже в комментариях выложены результаты теста на моём компьютере, соотношение скорости сортировки пузырьком и вставками указано в строке «Bubble/insertion sort time ratio»).
Кроме того, алгоритм быстрой сортировки [13] (который тоже имеет множество реализаций, ощутимо различающихся как по скорости, так и по глубине рекурсии) может модифицироваться таким образом, что при достижении некоторого порога размера массивов, на которые происходит деление исходного массива (скажем, когда элементов становится не больше 16-ти), либо при достижении определённой глубины рекурсии, сортировка переключается на… сортировку вставками! Казалось бы, зачем это делается, ведь сортировка вставками значительно медленнее быстрой сортировки? Однако на практике оказывается, что сортировка небольших массивов зачастую происходит чуть быстрее именно «вставками», нежели «быстрым» методом («quick/quick-insertion sort time ratio» в том же тесте по ссылке выше). Даже в тех случаях, когда скорость обоих методом примерно равная, глубина рекурсии уменьшается.
Какой вывод можно сделать из всего этого? Очень простой: теория – это хорошо, но она должна подкрепляться практикой. Как гласит японская пословица, знание является наградой за действие.
Автор: jin_x
Источник [14]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/algoritmy/338599
Ссылки в тексте:
[1] мышление: http://www.braintools.ru
[2] решета Эратосфена: https://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BE_%D0%AD%D1%80%D0%B0%D1%82%D0%BE%D1%81%D1%84%D0%B5%D0%BD%D0%B0
[3] Аткина: https://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BE_%D0%90%D1%82%D0%BA%D0%B8%D0%BD%D0%B0
[4] тест Миллера: https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D1%81%D1%82_%D0%9C%D0%B8%D0%BB%D0%BB%D0%B5%D1%80%D0%B0_(%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D1%87%D0%B8%D1%81%D0%B5%D0%BB)
[5] Миллера-Рабина: https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D1%81%D1%82_%D0%9C%D0%B8%D0%BB%D0%BB%D0%B5%D1%80%D0%B0_%E2%80%94_%D0%A0%D0%B0%D0%B1%D0%B8%D0%BD%D0%B0
[6] здесь: http://www.cyberforum.ru/blogs/521524/blog5712.html
[7] здесь: https://gist.github.com/jin-x/95d622ee52253c24e2ae40dce16c1b92
[8] быстрее, чем со связным списком: https://elizarov.livejournal.com/18000.html
[9] преждевременной оптимизации: https://elizarov.livejournal.com/17873.html
[10] сортировки пузырьком: https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%BF%D1%83%D0%B7%D1%8B%D1%80%D1%8C%D0%BA%D0%BE%D0%BC
[11] вставками: https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%81%D1%82%D0%B0%D0%B2%D0%BA%D0%B0%D0%BC%D0%B8
[12] сравнительный тест нескольких методов сортировки: https://gist.github.com/jin-x/e71ab51d7b78461df4da64968d592b34
[13] быстрой сортировки: https://ru.wikipedia.org/wiki/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0
[14] Источник: https://habr.com/ru/post/478420/?utm_campaign=478420&utm_source=habrahabr&utm_medium=rss
Нажмите здесь для печати.