Целые книги написаны по теории алгоритмов, но нам, простым смертным, которым не хочется влезать в дебри математики, но всë же любопытно узнать, как сравнивают алгоритмы по эффективности между собой, достаточно знать, что такое асимптотические нотации в общих чертах.
Допустим, у нас есть простейший алгоритм линейного поиска (то есть алгоритм, который перебирает последовательно все элементы массива друг за другом, в ходе этого запоминает индекс того элемента, значение которого равно искомому значению, а завершает работу, когда все элементы массива пройдены. То есть для искомого значения x, массива A с количеством элементов n:
- Присваиваем значение «не найдено» переменной Ответ.
- Для каждого индекса i (от 1 до n): 2А. Если A[i] = x, то присваиваем переменной Ответ значение i.
- Возвращаем значение переменной Ответ
Попробуем подсчитать примерное время выполнения алгоритма в зависимости от n.
Допустим, t1 — время на выполнение шага 1 (выполняется 1 раз), t3 — время на выполнение шага 3 (один раз), t2 — время на проверку условия в шаге 2 (n+1 раз), t2′ — время на инкремент в шаге 2 (выполняется n раз), t2A — время на проверку условия A[i] = x (выполняется n раз) и t2A’ — время на присваивание переменной Ответ = i (выполняется от 0 до n раз в зависимости от содержимого массива, в котором ищем значение).
Итак, в худшем случае имеем:
t1 + t2 * (n+1) + t2′ * n + t2A *n + t2A’ * n + t3 ,
а в лучшем:
t1 + t2 * (n+1) + t2′ * n + t2A *n + t2A’ * 0 + t3
Сгруппируем относительно переменного фактора n (все остальные величины — константы):
(t2 + t2′ + t2A) * n + (t1 + t2 + t3) в лучшем случае и
(t2 + t2′ + t2A + t2A’) * n + (t1 + t2 + t3) в худшем
В обоих случаях у нас многочлен типа a*n + b, где a и b — константы.
Мы видим, что при увеличении n все меньше значения будет играть b.
Не вдаваясь в определение асимптотической нотации, просто покажем, что это такое. У функции, зависящей от количества шагов алгоритма, приведенной к виду многочлена, убираем все младшие члены и коэффициент при старшем члене. То есть a*n + b превращается просто в n. Это называется тета (θ) функцией или нотацией. В нашем случае и в лучшем, и в худшем случае тета будет θ(n). Вообще, асимптотическая нотация для «худшего» случая называется O-нотацией, а для «лучшего» случая — омега (Ω)-нотацией. В нашем случае они совпадают. То есть при O-нотации O(n) мы показываем, что время выполнения алгоритма не может быть больше, чем n, помноженный на коэффициент. Младшими членами, как уже показано, при увеличении количества шагов алгоритма мы можем пренебречь. Например, если у нас функция, описывающая быстродействие алгоритма, вроде такой: t1 * n^2 + t2 * n + t3 , то тета-нотация будет такой: θ(n^2).
В целом, алгоритм с O(1) лучше, чем O(n), который лучше, чем алгоритм с O(n*log n) и т.д.
При сравнении конкретных алгоритмов надо помнить, что при малых значениях n нет смысла использовать эти нотации для сравнения, потому что в этом случае младшие члены многочленов могут быть даже больше, чем старшие. Однако, обычно алгоритмы все же используются для обработки больших объемов данных, и именно тогда имеет значение их эффективность.
Есть хорошая шпаргалка по эффективности основных алгоритмов и по различным видам асимптотических нотаций.
1 комментарий