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

Метод — это список однозначных команд, служащих для достижения цели. Метод, который всегда требует конечной серии операций, называется алгоритмом . Например, алгоритм сортировки карт представляет собой метод, где определены некие операции для сортировки колоды из 26 карт по масти и достоинству.

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 2.1.Оценка времени [22] Любезно предоставлено http://xkcd.com .

Временную сложность алгоритма определяют, подсчитывая основные операции, которые ему требуются для гипотетического набора входных данных объема 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 коробок. Сколько времени вам потребуется, чтобы расставить карточки в исходном порядке?