В предыдущей статье мы познакомились с понятием алгоритма и обсудили его свойства. Итак: одним из наиболее важных и используемых свойств алгоритмов является сложность, а, значит, при использовании различных алгоритмов очень важно уметь правильно её оценивать. Как раз об этом сегодня и пойдет речь.
В программировании, вычислительную сложность алгоритмов обычно оценивают по количеству действий, которые выполняет алгоритм и по количеству используемой памяти.
Чаще всего именно эти два критерия играют основную роль. Перед использованием алгоритма нужно правильно оценить, как именно сложность алгоритма будет зависеть от количества входных данных, чтобы «бесконечное» время работы алгоритма не стало сюрпризом в самый неподходящий момент.
Количество входных данных принято обозначать буквой n. Важно понимать, что нам нужно оценить не то, сколько именно операций потребуется алгоритму при конкретном количестве входных данных, а то, как он себя поведет при увеличении количества входных данных. То есть, мы хотим получить функцию изменения количества операций, которые выполнит алгоритм, в зависимости от количества входных данных n.
О-нотация
В подавляющем большинстве случаев для обозначения оценки сложности алгоритмов используют так называемую О-нотацию, в математике такое обозначение используют для сравнения асимптотического поведения функций.
О-нотация определяет функцию, назовем ее g(n), которая показывает, как будет изменяться вычислительная сложность алгоритма с изменением количества входных данных в худшем для алгоритма случае.
На самом деле всё очень просто. Постараемся объяснить на примере, скажем, алгоритма сортировки пузырьком.
При использовани алгоритма пузырьковой сортировки при каждом проходе по массиву попарно сравниваются элементы и, если нужно, меняются местами так, чтобы слева всегда был меньший элемент.
Оценим сложность этого алгоритма.
Допустим, на вход подается полностью отсортированный массив из 10 элементов, то есть n=10. Мы сравниваем все пары элементов от начала до конца, менять ничего не нужно. Таким образом за 10 операций сравнения на выходе мы получаем отсортированный массив. Вроде всё супер, алгоритм работает и очень быстро!
А что, если подать на вход массив, отсортированный в обратном порядке? Алгоритм этому точно не обрадуется. Ему придется выполнить 10 проходов по массиву и выполнить по 10 перестановок на каждом проходе, то есть выполнить 100 операций сравнения и перестановок.
Это худший случай для этого алгоритма, и мы видим, что в этом случае придется выполнить n2 операций. Получается, что сложность этого алгоритма может быть оценена как О(n2), то есть в этом случае наша искомая функция будет выглядеть вот так: g(n)=n2. Запись О(n2) как раз и говорит о том, что в худшем случае, для сортировки массива, состоящего из n элементов, нашему алгоритму придется выполнить n2 операций.
Зная это, мы можем примерно понять, какие объемы данных еще можно обрабатывать этим алгоритмом и для нас это будет приемлемо, а какие нет. Так как время работы, чаще всего, напрямую зависит от количества операций, рассмотрим абстрактный пример.
Например, для сортировки 1000 элементов алгоритму в худшем случае потребуется 1 секунда, тогда на сортировку 10000 элементов у алгоритма уйдет уже 100 секунд. Если мы захотим отсортировать 100000 элементов ждать придется уже почти 3 часа.
Отсюда можно сделать вывод, что стоит поискать другой алгоритм :)
_02174178.png)
Оценка лучшего и среднего случая
Как мы выяснили, О-нотация показывает худший случай, но что, если потребуется оценить среднее значение сложности или лучший случай?
Для обозначения оценки лучшего случая используется Ω-нотация, а для оценки среднего случая используется Θ-нотация.
Таким образом, для нашего алгоритма сортировки пузырьком верна будет запись:
О(n2) - в худшем случае, например, когда входные данные отсортированы в обратном порядке, вычислительная сложность алгоритма будет квадратично зависеть от количества элементов.
Θ(n2) - в среднем случае, когда данные перемешаны в случайном порядке вычислительная сложность алгоритма так же будет квадратично зависеть от количества элементов.
Ω(n) - в лучшем случае, когда входные данные уже отсортированы, нам все равно потребуется выполнить один проход по массиву, то есть произвести n операций.
Подведём итог
Итак, мы познакомились с тем, как оценивается сложность алгоритмов. Возможно, это не самый интересный материал, однако, понимание этих принципов необходимо для программистов. Мы еще не раз вернемся к оценке сложности алгоритмов, когда будем рассматривать различные полезные алгоритмы и надеемся, что по окончании цикла этих статей вопросов о том, как правильно оценивать сложность алгоритмов уже не останется.
P.S. Если эта статья была для тебя полезной, ставь 👍 и делись ей со своими друзьями!
