Доброго времени суток, читатели, зрители моего канала programmer's notes, любители языка Python. Не забывайте подписываться и писать свои
комментарии к моим статьям и видео.
Сложность алгоритмов
Сложность алгоритма имеет как минимум две стороны: скорость выполнения (временнАя сложность) и используемая память. Вторая сторона не всегда важна. Представьте, например, что вы сортируете массивы, размеры которых составляют несколько сотен элементов. Понятно, что уже не важно, использует ли данный алгоритм сортировки дополнительную память или нет. Но если ваш массив имеет размерность сотни тысяч, то тут для вас дополнительная память может играть важную роль.
Мы остановимся на сложности алгоритма, связанной со скоростью выполнения. Причем нас не должна интересовать скорость выполнения, которая связана с характеристиками компьютера. Как говорят, это оценка асимптотическая - какова зависимость скорости выполнения при увеличении некоторой характеристики (ик) обрабатываемых данных, которые обычно сводятся к размерности этих данных, например размерности массива. Обычно сложность обозначают так O(f(N)). Предполагается следующее: если размерность входных данных N растет, то скорость выполнения растет согласно функции f(N). При оценке сложность пользуются следующими правилами:
- Если функция, представляет собой сумму слагаемых, то выбирается слагаемое, которое растет быстрее всего. Например, если время растет по закону K*N*N*N + A*N*N + B*N, то считается только первое слагаемое, поскольку оно перекрывает рост второго и третьего слагаемых.
- Коэффициенты также не учитываются. Поэтому сложность алгоритма из пункта 1 будет O(N*N*N).
Конечно, вот такая асимптотическая оценка очень приблизительная. В общем случае все зависит от анализа входных данных. Например, поиск в неупорядоченном массиве имеет сложность O(N). Но это если мы вообще ничего не знаем о его структуре. Однако, если нужные нам данные находятся в начале массива (и мы это знаем), то сложность, возможно, будет совсем другой. Например, не зависящей от N.
Или, давайте рассмотрим известную всем пузырьковую сортировку (см. статью).
Программа довольно проста. Поскольку на каждую итерацию внешнего цикла приходится в среднем количество итераций пропорциональных N, то сложность такого алгоритма будет O(N*N). Но это в общем случае. Можно сказать, что это верхняя граница. А вот представьте себе, что мы имеем уже упорядоченный массив или частично упорядоченный. Оказывается, что в этом случае внутренний цикл будет выполняться только 1-2 раза. А это уже совсем другая сложность O(N). Таким образом мы получили нижнюю границу сложности алгоритма. Так вот во многих случаях приходится оценивать верхнюю и нижнюю границу сложности. Более того, на основе большого количества экспериментов, можно получить и среднюю оценку. В конкретных случаях это может быть очень важным показателем.
Проведем два эксперимента, иллюстрирующих сложность алгоритма для сортировки пузырьком для случаев массива заполненного случайными числами и массивов уже отсортированных.
Рассмотрим данную программу. Программа измеряет времена сортировки. При этом сравниваются коэффициенты: (n/n1) и sqrt(dt/dt1). Конечно они точно никогда не совпадут, но четко видно (см. рисунок ниже), порядок их остается приблизительно одинаков. Т.е. время сортировки растет согласно сложности O(N * N).
Рассмотрим теперь такую программу. Программа измеряет времена сортировки уже отсортированных массивов. При этом сравниваются коэффициенты: n/n1 и dt/dt1. Из рисунка 2 видно, что они имеют один и тот же порядок, т.е. подтверждается сложность алгоритма O(N).
Всего доброго и до встречи на моем канале programmer's notes. Подписывайтесь, ставьте лайки и комментируйте статьи канала.