Теоретический минимум по Computer Science - [8]

На меньшее количество операций нужно меньше вычислительной мощности. Нам нравятся быстрые решения, поэтому мы следим за числом операций в наших алгоритмах. В случае со многими алгоритмами необходимое число операций быстро растет с увеличением объема входных данных. В нашем случае может потребоваться всего несколько операций для сортировки 26 карт, но в четыре раза больше операций для сортировки 52 карт!

Чтобы избежать непредвиденных сложностей, связанных с раздуванием задачи, нужно узнать временную сложность алгоритма. В этой главе пойдет речь о том, как:

рассчитывать и интерпретировать временные сложности;

выражать их рост при помощи необычной нотации «О большое»;

избегать экспоненциальных алгоритмов;

убедиться, что у вашего компьютера достаточно памяти.

Но прежде нам предстоит узнать, как определяется временная сложность алгоритма.

Временная сложность записывается как: T(n). Она показывает количество операций, которые алгоритм выполняет при обработке входящих данных объема n. Также T(n) называют стоимостью выполнения алгоритма. Если наш алгоритм сортировки игральных карт подчиняется T(n) = n², то мы можем предсказать, насколько больше потребуется времени, чтобы отсортировать колоду двойного размера:

.

Надейтесь на лучшее, но готовьтесь к худшему

Будет ли быстрее отсортирована колода карт, которая уже почти упорядочена? Объем входящих данных — не единственная характеристика, влияющая на количество требуемых алгоритмом операций. Когда алгоритм может иметь разные значения T(n) для одного n, мы обращаемся к случаям, или, говоря по-другому, вариантам развития событий.

• Лучший случай — это ситуация, когда для любых входящих данных установленного объема требуется минимальное количество операций. В сортировке такое происходит, когда входящие данные уже упорядочены.

• Худший случай — когда для любых входящих данных данного объема требуется максимальное количество операций. Во многих алгоритмах сортировки такое случается, когда данные на входе передаются в обратном порядке.

• Средний случай предполагает среднее количество операций, обычно нужных для обработки входящих данных этого объема. Для сортировки средним считается случай, когда входящие данные поступают в произвольном порядке.

Худший случай — самый важный из всех. Ориентируясь на него, вы обеспечиваете себе гарантию. Когда ничего не говорится о сценарии, ориентируйтесь на худший случай. Далее мы узнаем, как на практике анализировать события c учетом худшего варианта их развития.

Рис. 2.1. Оценка времени[22]

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 всегда соблюдается. Это означает, что внутренний цикл выполнит одно сравнение и одно присвоение

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

T(n) = n² + 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² + n — 2. Наиболее быстро растущим членом является n², поэтому мы можем записать T(n) ≈ n². Приняв, что в одной коробке лежит