Владстон Феррейра Фило - Теоретический минимум по Computer Science [Все что нужно программисту и разработчику]

Временную сложность алгоритма определяют, подсчитывая основные операции, которые ему требуются для гипотетического набора входных данных объема 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 итераций и в каждой из них выполнит две операции (одно присвоение и один обмен значениями), всего 2 n -2 операций. Внутренний цикл сначала выполнится n — 1 раз, затем n — 2 раза, n — 3 раза и т. д. Мы уже знаем, как суммировать эти типы последовательностей [24] (см. раздел «Комбинаторика»). :

В худшем случае условие if всегда соблюдается. Это означает, что внутренний цикл выполнит одно сравнение и одно присвоение раз, отсюда n 2— n операций. В целом стоимость алгоритма 2 n — n складывается из операций внешнего цикла и n 2операций внутреннего цикла. Мы получаем временную сложность:

T ( n ) = n 2+ n — 2.

Что дальше? Если размер нашего списка был n = 8, а затем мы его удвоили, то время сортировки увеличится в 3,86 раза:

.

Если мы снова удвоим размер списка, нам придется умножить время на 3,9. Дальнейшие удвоения дадут коэффициенты 3,94, 3,97, 3,98. Заметили, как результат становится все ближе и ближе к 4? Это значит, что сортировка 2 млн элементов потребует в четыре раза больше времени, чем сортировка 1 млн элементов.

Допустим, объем входящих данных алгоритма очень велик, и мы его еще увеличиваем. Чтобы предсказать, как изменится время выполнения, нам не нужно знать все члены функции T ( n ). Мы можем аппроксимировать T ( n ) по ее наиболее быстрорастущему члену, который называется доминантным членом .

Учетные карточки Вчера вы опрокинули коробку с учетными карточками, и вам пришлось потратить два часа на сортировку выбором, чтобы все исправить. Сегодня вы рассыпали 10 коробок. Сколько времени вам потребуется, чтобы расставить карточки в исходном порядке?

Мы уже убедились, что сортировка выбором подчиняется T ( n ) = = n 2+ n — 2. Наиболее быстро растущим членом является n 2, поэтому мы можем записать T ( n ) ≈ n 2. Приняв, что в одной коробке лежит n карточек, мы находим:

Вам потребуется приблизительно 100 × (2 часа) = 200 часов! А что, если сортировать по другому принципу? Например, есть метод под названием «сортировка пузырьком», временная сложность которого определяется формулой T ( n ) = 0,5 n 2+ 0,5 n . Наиболее быстро растущий член тогда даст T ( n ) ≈ 0,5 n 2, следовательно:

Рис. 2.2.Уменьшение масштаба n 2, n 2+ n — 2 и 0,5 n 2+ 0,5 n с увеличением n

Коэффициент 0,5 сам себя аннулирует! Понять мысль, что оба выражения — n 2— n — 2 и 0,5 n 2+ 0,5 n — растут как n 2, не так-то просто. Почему доминантный член функции игнорирует все другие числа и оказывает наибольшее влияние на рост? Давайте попытаемся эту концепцию представить визуально.