Про асимптотики и реальность

Добрый вечер, уважаемые читатели. Сегодня я бы хотел немного побыть капитаном очевидностью и высказать несколько всем известных фактов про оценку сложности алгоритмов.

Часто, когда мы решаем ту или иную задачу, мы ищем готовые алгоритмы. Думаю, всем очевидно, что на промышленной задачи никто не будет использовать сортировку, отличную от той, что встроена в стандартную библиотеку языка программирования.

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

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

В CS-сфере принято оценивать алгоритмы в нотации «О-большое». Ведь это так здорово. Всегда можно отбросить константу, основание алгоритма, да и сделать кучу других действий, которые нам прощает «большая ош-ка».

Но так ли хороша на самом деле эта нотация? Сегодня я ещё раз убедился, что It Depends. Если мы занимаемся теоретическими исследованиями, то, пожалуй, да, нотация хороша. Но если мы начинаем писать код, то уже нужно быть кранйе осторожным.

Первая проблема, с которой мы сможем встретиться — это огромная константа. Например, алгоритм работает за O(n). Это означает, что T(n) = C*n, где T(n) — функция зависимости времени от количества элементов, а C — произвольная константа. Что лучше, T(n) = 9999*n, или T(n) = 0.0001*n*n? Это зависит. Если у вас данных мало, то, очевидно, что вторая функция будет на порядок меньше. А значит и выбирать следует второй алгоритм. Ну, а если у вас действительно бесконечное количество данных (хе-хе), то выбор очевиден.

Вторая проблема — это скрытие под Этой нотацией различных функций, зависящих от n, которые растут медленнее на бесконечности, чем та, которая указана в O. Эта проблема, конечно же, является лишь частным случаем первой, но я решил выделить её отдельно.

Приведу пример. У вас есть некоторая сортировка, работающая за O(n * log(n)). Что это нам говорит? Скорей всего, что существует дерево рекурсии, длина которого как раз таки логорифмическая. А знаем ли мы, сколько других действий выполнялось за Линию? Может, там ещё 10 итераций по всем данным было, перед тем, как началась сортировка из 20 элементов. На бумаге это не важно, но в жизни, думаю, очевидно, что это не так.

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

Категории: Программирование