2.1. Оценка затрат времени
Временную сложность алгоритма определяют, подсчитывая основные операции, которые ему требуются для гипотетического набора входных данных объема n. Мы продемонстрируем это на примере сортировки выбором, алгоритма сортировки с вложенным циклом. Внешний цикл for обновляет текущую позицию, с которой ведется работа, внутренний цикл for выбирает элемент, который затем подставляется в текущую позицию
[23]:
function selection_sort(list)
····for current ← 1 … list.length — 1
········smallest ← current
········for i ← current + 1 … list.length
············if list[i] < list[smallest]
················smallest ← i
·······list.swap_items(current, smallest)
Давайте посмотрим, что произойдет со списком из n элементов в худшем случае. Внешний цикл совершит n — 1 итераций и в каждой из них выполнит две операции (одно присвоение и один обмен значениями), всего 2n-2 операций. Внутренний цикл сначала выполнится n — 1 раз, затем n — 2 раза, n — 3 раза и т. д. Мы уже знаем, как суммировать эти типы последовательностей
[24]:
В худшем случае условие if всегда соблюдается. Это означает, что внутренний цикл выполнит одно сравнение и одно присвоение
раз, отсюда n2 — n операций. В целом стоимость алгоритма 2n — n складывается из операций внешнего цикла и n2 операций внутреннего цикла. Мы получаем временную сложность:
T(n) = n2 + n — 2.
Что дальше? Если размер нашего списка был n = 8, а затем мы его удвоили, то время сортировки увеличится в 3,86 раза:
.
Если мы снова удвоим размер списка, нам придется умножить время на 3,9. Дальнейшие удвоения дадут коэффициенты 3,94, 3,97, 3,98. Заметили, как результат становится все ближе и ближе к 4? Это значит, что сортировка 2 млн элементов потребует в четыре раза больше времени, чем сортировка 1 млн элементов.
Понимание роста затрат
Допустим, объем входящих данных алгоритма очень велик, и мы его еще увеличиваем. Чтобы предсказать, как изменится время выполнения, нам не нужно знать все члены функции T(n). Мы можем аппроксимировать T(n) по ее наиболее быстрорастущему члену, который называется доминантным членом.
Учетные карточки
Вчера вы опрокинули коробку с учетными карточками, и вам пришлось потратить два часа на сортировку выбором, чтобы все исправить. Сегодня вы рассыпали 10 коробок. Сколько времени вам потребуется, чтобы расставить карточки в исходном порядке?
Мы уже убедились, что сортировка выбором подчиняется T(n) = = n2 + n — 2. Наиболее быстро растущим членом является n2, поэтому мы можем записать T(n) ≈ n2. Приняв, что в одной коробке лежит n карточек, мы находим:
Вам потребуется приблизительно 100 × (2 часа) = 200 часов! А что, если сортировать по другому принципу? Например, есть метод под названием «сортировка пузырьком», временная сложность которого определяется формулой T(n) = 0,5n2 + 0,5n. Наиболее быстро растущий член тогда даст T(n) ≈ 0,5n2, следовательно:
Рис. 2.2. Уменьшение масштаба n2, n2 + n — 2 и 0,5n2 + 0,5n с увеличением n
Коэффициент 0,5 сам себя аннулирует! Понять мысль, что оба выражения — n2 — n — 2 и 0,5n2 + 0,5n — растут как n2, не так-то просто. Почему доминантный член функции игнорирует все другие числа и оказывает наибольшее влияние на рост? Давайте попытаемся эту концепцию представить визуально.
На рис. 2.2 изображены графики двух временных сложностей, которые мы рассмотрели, рядом с графиком n2 на разных уровнях масштабирования. По мере увеличения значения n графики, судя по всему, становятся все ближе и ближе. На самом деле вместо точек в функции T(n) = ∙ n2 + ∙ n + ∙ вы можете подставить любые числа, и она по-прежнему будет расти как n2.
Запомните, такой эффект сближения кривых работает, если наиболее быстро растущий член — одинаковый. График функции с линейным ростом (n) никогда не будет сближаться с графиком квадратичного роста (n2), который, в свою очередь, никогда не догонит график, имеющий кубический рост (n3).
