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

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

• Дискретная математика и ее применения, 7-е издание (Discrete Mathematics and Its Applications, см. https://code.energy/rosen).

• Слайды профессора Жаннет Уинг, иллюстрирующие вычислительное мышление, см. https://code.energy/wing.

Сколько времени потребуется, чтобы разложить по порядку 26 перетасованных карт? А если у вас будет 52 карты, уйдет ли на эту же операцию вдвое больше времени? И насколько больше его потребуется на тысячу карточных колод? Ответ неразрывно связан с методом, который используется для сортировки карт.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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