Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 13
Текст из файла (страница 13)
В общем случае время работы алгоритма увеличивается с увеличением количества входных данных, поэтому общепринятая практика— представлять время работы программы как функцию, зависящую от количества входных элементов. Для этого понятия "время работы алгоритма" и "размер входных данных" нужно определить точнее. Наиболее адекватное понятие размера входных данных (шрш з1ге) зависит от рассматриваемой задачи. Во многих задачах, таких как сортировка или дискретные преобразования Фурье, это количество входных элементов, например, размер п сортируемого массива.
Для многих других задач, таких как перемножение двух целых чисел, наиболее подходящая мера для измерения размера ввода — общее количество битов, необходимых для представления входных данных в обычных двоичных обозначениях. Иногда размер ввода удобнее описывать с помощью не одного, а двух чисел. Например, если на вход алгоритма подается граф, размер ввода можно описывать, указывая количество вершин и ребер графа. Для каждой рассматриваемой далее задачи будет указываться способ измерения размера входных данных. Время работы алгоритма для того или иного ввода измеряется в количестве элементарных операций, или "шагов", которые необходимо выполнить.
Здесь удобно ввести понятие шага, чтобы рассуждения были как можно более машинно- Глава 2. Приступаем к изучению 67 1)чвбятю)ч Бокт(А) время ) 1ог 7' — 2 Го 1еидйз(А] с) 2 до йеу — А(3] С2 3 5ь Вставка элемента А[3] в отсортированную последовательность А[1..7 — Ц. О 4 з д — 1 С4 5 тчййе з > О аль А[з] > )сеу С5 6 По А[а+ 1] — А[з] Сб 7 — з — 1 Ст 8 А[а+ 1] — йеу Са количество раз и — 1 и — 1 и — 1 2," 2(г, — 1) х 1=2 (ту 1) и — 1 Время работы алгоритма — зто сумма промежутков времени, необходимых для выполнения каждой входящей в его состав исполняемой инструкции.
Если вы- 'Здесь есть некоторые тонкие нюансы. Шаги вычислений, описанные на обычном языке, часто представляют собой разновидности процелур, состояших из нескольких элементарных инструкций. Например. далее в этой книге может встретиться строка "сортировка точек по координате к". Как вы увидите, эта команда требует больше, чем постоянного количестна времени работы. Заметим также, что команда вызова подпрограммы выполняется в течение фиксированного времени, однако сколько длится выполнение вызванной подпрограммы — это зависит от ее сложности. Таким образом, процесс вызова подпрограммы (передача в нее параметров и т.п.
действия) следует отличать от выполнения этой подпрограммы. независимыми. На данном этапе мы будем исходить из точки зрения, согласно которой для выполнения каждой строки псеводкода требуется фиксированное время. Время выполнения различных строк может отличаться, но мы предположим, что одна и та же з-я строка выполняется за время оп где с, — константа. Эта точка зрения согласуется с моделью ВАМ и отражает особенности практической реализации псевдокода на реальных компьютерах".
В последующих рассуждениях формула для выражения времени работы алгоритма 1)сбавят)оы Бокт, которая сначала будет сложным образом зависеть от всех величин с„значительно упростится благодаря более лаконичным обозначениям, с которыми проще работать. Эти более простые обозначения позволят легче определить, какой из двух алгоритмов эффективнее. Начнем с того, что введем для процедуры 1)чбййт)о)ч Войт время выполнения каждой инструкции и количество их повторений. Для каждого д = 2,3,...,и, где и = 1еидЖ (А], обозначим через г, количество проверок условия в цикле тчЬПе (строка 5).
При нормальном завершении циклов аког или чгЬПе (т.е. когда перестает выполняться условие, заданное в заголовке цикла) условие проверяется на один раз больше, чем выполняется тело цикла. Само собой разумеется, мы считаем, что комментарии не являются исполняемыми инструкциями, поэтому они не увеличивают время работы алгоритма: Часть 1. Основы 68 полнение инструкции длится в течение времени с; и она повторяется в алгоритме гг раз, то ее вклад в полное время работы алгоритма равно снкз Чтобы вычислить время работы алгоритма 1ызект~оы Болт (обозначим его через Т (и)), нужно просуммировать произведения значений, стоящих в столбцах время и кодичеслгво раз, в результате чего получим: Т (гт) = Сггт+ С2 (гг — 1) + С4 (гг — 1) + С5 ~~г ьу+ Сб ~ (ьу — 1)+ 1=2 5=2 п + ст ~ (~у — 1) + са (и - 1) .
3=2 Даже если размер входных данных является фиксированной величиной, время работы алгоритма может зависеть от степени упорядоченности сортируемых величин, которой они обладали до ввода. Например, самый благоприятный случай для алгоритма 1г48ектюы Зонт — это когда все элементы массива уже отсортированы. Тогда для каждого з = 2, 3,..., и получается, что А [з] < кеу в строке 5, еще когда т равно своему начальному значению т' — 1. Таким образом, при у' = = 2,3,...,и 4 = 1, и время работы алгоритма в самом благоприятном случае вычисляется так: Т (и) = сггз+ с2 (и 1) + с4 (гт 1) + с5 (гт 1) + са (гт 1) = (С1 + С2 + С4 + С5 + С8) Гà — (С2 + С4 + С5 + С8) Это время работы можно записать как агг + б, где а и 6 — константы, зависящие от величин с;; т.е.
это время является линейной фуикг4ией от ьь Если элементы массива отсортированы в порядке, обратном требуемому (в данном случае в порядке убывания), то это наихудший случай. Каждый элемент А [Я необходимо сравнивать со всеми элементами уже отсортированного подмножества А [1.. т' — 1[, так что для т' = 2, 3,..., гг значения т = у. С учетом того, что т гг(п+ 1) ,7 э= 3=2 гт (гг — 1) 2 О-1)= 2 3=2 ~Это правило не всегда применимо к такому ресурсу, как память. Если инструкпия оперирует с т словами памяти и выполняется и раз, то это егпе не означает, что всего при этом потребляется гии слов памяти. Глава 2.
Приступаем к изучению 69 (как выполняется это суммирование, показано в приложении А), получаем, что время работы алгоритма 1мзнкт|он Зонт в худшем случае определяется соотношением 2 (п) = с1п + сз (п — 1) + С4 (п 1) + с5 /п(п+ 1) 2 -)+ +сб +с7 +са(п — 1) = =( С5 С6 С7~ З / С5 С5 С7 — + — + — ~ и + ~С7 + сз + с4 + — — — — — + са) и— 2 2 2~ 2 2 2 (СЗ + С4 + С5 + С8) . Это время работы можно записать как апз + Ьп+ с, где константы а, Ь и с зависят от с;. Таким образом, это квадратичная функция от и. Обычно время работы алгоритма фиксировано для определенных входных данных, как в случае сортировки вставкой, однако в последующих главах мы ознакомимся с некоторыми интересными алгоритмами, поведение которых носит вероятностный характер.
Время их работы может меняться даже для одних и тех же входных данных. Наихудшее и среднее время работы Анализируя алгоритм, работающий по методу вставок, мы рассматривали как наилучший, так и наихудший случай, когда элементы массива были рассортированы в порядке, обратном требуемому. Далее в этой книге мы будем уделять основное внимание определению только времени работы в на44худи4ем случае, т.е.
максимальном времени работы из всех входных данных размера п. Тому есть три причины. ° Время работы алгоритма в наихудшем случае — это верхний предел этой величины для любых входных данных. Располагая этим значением, мы точно знаем, что для выполнения алгоритма не потребуется большее количество времени. Не нужно будет делать каких-то сложных предположений о времени работы и надеяться, что на самом деле эта величина не будет превышена. ° В некоторых алгоритмах наихудший случай встречается достаточно часто.
Например, если в базе данных происходит поиск информации, то наихудшему случаю соответствует ситуация, когда нужная информация в базе данных отсутствует. В некоторых поисковых приложениях поиск отсутствующей информации может происходить довольно часто. ° Характер поведения "усредненного" времени работы часто ничем не лучше поведения времени работы для наихудшего случая. Предположим, что последовательность, к которой применяется сортировка методом вставок, Часть 1.
Основы 70 сформирована случайным образом. Сюлько времени понадобится, чтобы определить, в какое место подмассива А [1..7' — Ц следует поместить элемент А [7]? В среднем половина элементов подмассива А [1..7' — Ц меньше, чем А [7'], а половина — больше его. Таким образом, в среднем нужно проверить половину элементов подмассива А [1.. 7' — Ц, поэтому г приблизительно равно у/2.
В результате получается, что среднее время работы алгоритма является квадратичной функцией от количества входных элементов, т.е. характер этой зависимости такой же, как и для времени работы в наихудшем случае. В некоторых частных случаях нас будет интересовать среднее время работы алгоритма, или его математическое ожиданиеб. В главе 5 будет продемонстрирован метод вероятностного анализа, позволяющий определить ожидаемое время работы. Однако при анализе усредненного времени работы возникает одна проблема, которая заключается в том, что не всегда очевидно, какие входные данные для данной задачи будут "усредненными". Часто делается предположение, что все наборы входных параметров одного и того же обьема встречаются с одинаковой вероятностью.
На практике это предположение может не соблюдаться, однако иногда можно применять рандомизированные алгоритмы, в юторых используется случайный выбор, и это позволяет провести вероятностный анализ. Порядок возрастания Для облегчения анализа процедуры 1мзпктюм Яокт были сделаны неюторые упрощающие предположения. Во-первых, мы проигнорировали фактическое время выполнения каждой инструкции, представив эту величину в виде некоторой константы с;. Далее мы увидели, что учет всех этих констант дает излишнюю информацию: время работы алгоритма в наихудшем случае выражается формулой апз + Ьп + с, где а, Ь, и с — некоторые константы, зависящие от стоимостей с;ч Таким образом, мы игнорируем не только фактические стоимости команд, но и их абстрактные стоимости сч Теперь введем еще одно абстрактное понятие, упрощающее анализ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
