Асимптотическая сложность алгоритмов: что за зверь?

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

Асимптотическая сложность алгоритмов представляет собой время и память, которые понадобятся вашей программе в процессе экзекуции. Одно дело – знать, что существуют линейные или логарифмические алгоритмы, но совсем другое – понимать, что же за всем этим стоит.

С помощью Big O Notation можно математически описать то, как поведет себя программа в условиях наихудшего сценария при большом количестве входных данных. Например, если вы используете сортировку пузырьком, чтобы отсортировать элементы в целочисленном массиве по возрастанию, то худшим сценарием в этом случае будет отсортированный в убывающем порядке массив. При таком раскладе вашему алгоритму понадобится наибольшее количество операций и памяти.

Разобравшись в принципе работы Big O Notation, вы сможете решить проблему оптимизации ваших программ и добиться максимально эффективного кода.

Сложности О(1) и O(n) самые простые для понимания.

О(1) означает, что данной операции требуется константное время. Например, за константное время выполняется поиск элемента в хэш-таблице, так как вы напрямую запрашиваете какой-то элемент, не делая никаких сравнений. То же самое относится к вызову i-того элемента в массиве. Такие операции не зависят от количества входных данных.

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

Бинарный поиск является одним из классических примеров алгоритмов, работающих за O(log_2(n)). Каждая операция уменьшает количество входных данных вдвое.

Например, если у вас есть отсортированный массив, насчитывающий 8 элементов, в худшем случае вам понадобится сделать Log_2(8)=3 сравнений, чтобы найти нужный элемент.

Рассмотрим отсортированный одномерный массив с 16 элементами:

Допустим, нам нужно найти число 13.

Мы выбираем медиану массива и сравниваем элемент под индексом 7 с числом 13.

Так как наш массив отсортирован, а 16 больше, чем 13, мы можем не рассматривать элементы, которые находятся под индексом 7 и выше. Так мы избавились от половины массива.

Дальше снова выбираем медиану в оставшейся половине массива.

Сравниваем и получаем, что 8 меньше, чем 13. Уменьшаем массив вдвое, выбираем элемент посередине и делаем еще одно сравнение. Повторяем процесс, пока не останется один элемент в массиве. Последнее сравнение возвращает нужный элемент. Лучшее развитие событий – если первая выбранная медиана и есть ваше число. Но в худшем случае вы совершите log_2(n) сравнений.

Сложность O(n*log n) можно представить в виде комбинации O(log n) и O(n). Такую сложность можно получить, если в вашей программе есть один for-цикл, который содержит еще один for-цикл. То есть нестинг циклов, один из которых работает за O(log n), а другой – за O(n).

Сложность O(n^2) встречается довольно часто в алгоритмах сортировки. Ее легко можно получить, если в программе имплементировать нестинг двух for-циклов, работающих в O(n).

Например:

То же самое произойдет, если вам надо будет пройтись по элементам двумерного массива.

Алгоритмы, которые можно описать с помощью нотации O(n^2 + n + 3) или O(n^2-100000), или даже O(n^2 + 100000000) все равно считаются квадратными. При большом количестве входных данных только наибольшая степень n является важной. Константы и коэффициенты обычно не берут во внимание. То же самое касается линейных и логарифмических функций. O( n +1000) и O(1000*n) все равно будут работать в O(n).

Использование алгоритмов, которые работают в O(n^2) и выше (например, экспоненциальная функция 2^n), является плохой практикой. Следует избегать подобных алгоритмов, если хотите, чтобы ваша программа работала за приемлемое время и занимала оптимальное количество памяти.

Источник: proglib.io

Комментарии: