Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013), страница 10

Анализ сортировки вставкой Время работы процедуры 1мзпктюм-Бокт зависит от набора входных значений: для сортировки тысячи чисел требуется больше времени, чем для сортировки трех чисел, Кроме того, время сортировки с помощью этой процедуры может быть разным для последовательностей, состоящих из одного и того же количества элементов, в зависимости от степени упорядоченности этих последовательностей до начала сортировки. В общем случае время работы алгоритма увеличивается с увеличением количества входных данных, поэтому общепринятая практика— представлять время работы программы как функцию, зависящую от количества входных элементов. Для этого понятия "время работы алгоритма" и "размер входных данных" нужно определить точнее.

Наиболее адекватное понятие размера входных данных (1прц~ з)ге) зависит от рассматриваемой задачи. Во многих задачах, таких как сортировка или дискретные преобразования Фурье, это количество входных элементов, например размер и сортируемого массива. Для многих других задач, таких как перемножение двух целых чисел, наиболее подходящая мера для измерения размера ввода — общее количество битов, необходимых для представления входных данных в обычных двоичных обозначениях. Иногда размер ввода удобнее описывать с помощью не одного, а двух чисел. Например, если на вход алгоритма подается граф, размер ввода можно описывать, указывая количество вершин и ребер графа. Для каждой рассматриваемой далее задачи будет указываться способ измерения размера входных данных.

Время работы алгоритма для тех или иных входных данных измеряется в количестве элементарных операций, или "шагов", которые необходимо выполнить. Здесь удобно ввести понятие шага, чтобы рассуждения были как можно более машинно-независимыми. На данном этапе мы будем исходить из точки зрения, согласно которой для выполнения каждой строки псеводкода требуется фикси- Часть 1 Ослоеы 1)цзект!О)ч-БОкт(А) 1 1ог д' = 2 То А. 1епдбгг 2 /сед = АЯ 3 // Вставка АЦ в отсортированную последовательность А(1 ..

д — Ц. 4 з=7 — 1 5 чрЬНе з > О и А)з) > )сеу б А(з+ Ц = А(з~ 7 з=т — 1 8 А(з+ Ц = )сеу Стоимость Повторы с) С2 п — 1 и — 1 х-у=2 11 4 7=2( у 1) Е; 2(1,-1) и — 1 С4 сб с7 сб Время работы алгоритма — это сумма промежутков времени, необходимых для выполнения каждой входящей в его состав выполняемой инструкции.

Если выполнение инструкции длится в течение времени с, и она повторяется в алгоритме и раз, то ее вклад в полное время работы алгоритма равен с,пб. Чтобы вычислить время работы алгоритма 1р)еект)ор)-Бокт (обозначим его через Т(п)), нужно просуммировать произведения значений, стоящих в столбцах спчоимость з здесь есть некоторые нюансы Шаги вычислений, описанные на обычном языке, часто представляют собой рюновидности процедур, состоящих из нескольких элементарных инструкций, имеющих более чем константное время работы.

Например, далее в этой книге может встретиться строка "сортировка точек по координате хз Как вы увидите, эта команда требует больше чем постоянного количества времени работы. Заметим также, что команда вызова подпрограммы выполняетсн в течение фиксированного времени, однако сколько длитс» выполнение вызванной подпрограммы, зависит ог ее сложности. Таким образом, процесс вызова подпрограммы Гпередачу в нее параметров и другие действия) следует отличать от пропесса емлаеиения этой подпрограммы. еЭго правило ие всегда применимо к такому ресурсу, как память. Если инструкция оперирует пг словами памяти и выполняется и раз, то это еще не означает, что всего при этом потребляется тп слов памяти.

рованное время. Время выполнения различных строк может различаться, но мы предположим, что одна и та же з-я строка выполняется за время сг, где с, — константа. Эта точка зрения согласуется с моделью зхАМ и отражает особенности практической реализации псевдокода на реальных компьютерах . В последующем рассмотрении формула для выражения времени работы алгоритма 1)цзект)О)4-БОкт, которая сначала будет сложным образом зависеть от всех величин с„значительно упростится благодаря более лаконичным обозначениям, с которыми проще работать.

Эти более простые обозначения позволят легче определить, какой из двух алгоритмов эффективнее. Начнем с того, что введем для процедуры 1)цзект)О)ц-Бокт временную "стоимость'" каждой инструкции и количество их повторений. Для каждого д 2,3,...,и, где и = А.1епдр)ь, обозначим через б количество проверок условия в цикле чрй11е (строка 5). При нормальном завершении циклов Гог и зрй11е (т.е. когда перестает выполняться условие, заданное в заголовке цикла) условие проверяется на один раз больше, чем выполняется тело цикла. Само собой разумеется, мы считаем, что комментарии не являются исполняемыми инструкциями, поэтому они не увеличивают время работы алгоритма.

4Р Глава 2. Приетунаеи к изучению и ловзяоры, в результате чего получим и н Т(п) = сзп+ с2(п — 1) + с4(п — 1) + с5 ~~~ вз + сб~~~ (вз — 1) 3'=2 з=г + с7 ~~ (вз — 1) + сб(п — 1) 7=2 Даже если размер входных данных является фиксированной величиной, время работы алгоритма может зависеть от самих входных данных — степени упорядоченности сортируемых величин, которой они обладали до ввода. Например, самый благоприятный случай для алгоритма 1мзнктюн-Болт — это когда все элементы массива уже отсортированы. Тогда для каждого 7' = 2, 3,..., п мы находим, что А[4] < Ьеу в строке 5, еще когда з' равно своему начальному значению з — 1. Таким образом, г; = 1 для 7' = 2, 3,..., п, и время работы алгоритма в самом благоприятном случае вычисляется так: Т(п) = сзп+ с2(п — 1) + с4(зъ — 1) + сб(п — 1) + сб(п — 1) = (С1 + С2 + С4 + С5 + С8)П вЂ” (С2 + С4 + С5 + С8) .

Это время работы можно записать как ап + Ь, где а и Ь вЂ” консгланязы, зависящие от величин с,; т.е. это время является линейной функцией от п. Если же массив находится в порядке, обратном требуемому (т.е. в порядке убывания элементов), то реализуется наихудший случай. При этом мы должны сравнивать каждый элемент А[А с каждым элементом всего отсортированного подмассива А[1 ..

7' — 1[, так что г = 7' для 7' = 2, 3,..., п, Заметив, что ч п(п+ 1) ~3= 2 з=г п(п — 1) 2 (2 — ')= з=г (см. обзор, посвященный таким суммам, в приложении А), мы находим, что в наи- худшем случае время работы 1148иктюн-Бокт составляет /п(п+ 1) Т(п) = сзп+ с2(п 1) + с4(п 1) + с5 2 -) +сб +сг +са(п 1) =( Сб Сб С71 2 / Сб Сб С7 — + — + — ) П + ( С1 + С2 + С4 + — — — — — + С8) П 2 2 2з' 2 2 2 — (С2 + С4 + С5 + С8) 50 Часть!.

Основы Это время работы в наихудшем случае можно записать как апз + Ьп + с, где а, Ь и с — константы, зависящие от стоимостей с;; таким образом, мы имеем квадратичную функцию от и. Обычно время работы алгоритма для определенных входных данных фиксировано, как в случае сортировки вставкой, однако в последующих главах мы ознакомимся с некоторыми интересными "рандомизированными" алгоритмами, поведение которых носит вероятностный характер. Время их работы может меняться даже для одних и тех же входных данных.

Наихудшее и среднее время работы Анализируя алгоритм сортировки вставкой, мы рассматривали как наилучший, так и наихудший случай, когда элементы массива были рассортированы в порядке, обратном требуемому. Далее в этой книге мы будем уделять основное внимание определению только времени работы в наидудиеен случае, т.е. максимального времени работы для любых входных данных размером п. На то есть три причины. Время работы алгоритма в наихудшем случае — это верхний предел этой величины для любых входных данных. Располагая этим значением, мы точно знаем, что для выполнения алгоритма не потребуется большее количество времени.

Не нужно будет делать каких-то сложных предположений о времени работы и надеяться, что на самом деле эта величина не будет превышена. В некоторых алгоритмах наихудший случай встречается достаточно часто. Например, если в базе данных происходит поиск информации, то наихудшему случаю соответствует ситуация, когда нужная информация в базе данных отсутствует. В некоторых приложениях поиск отсутствующей информации может происходить довольно часто, Характер поведения "усредненного" времени работы часто ничем не лучше поведения времени работы для наихудшего случая. Предположим, что последовательность, к которой применяется сортировка методом вставок, сформирована случайным образом. Сколько времени понадобится, чтобы определить, в какое место подмассива А[1 ..

у — 1[ следует поместить элемент АЦ? В среднем половина элементов подмассива А[1 .. у — 1] меньше, чем А[?1, а половина — больше этого значения. Таким образом, в среднем нужно проверить половину элементов подмассива А[1 ., з — 1[, поэтому т приблизительно равно ,?/2. В результате получается, что среднее время работы алгоритма является квадратичной функцией ог количества входных элементов, т.е, характер этой зависимости такой же, как и для времени работы в наихудшем случае. В некоторых частных случаях нас будет интересовать среднее время работы алгоритма, или его математическое ожидание, Позже будет продемонстриро- "дааее в книге строгий термин "математическое ожидание" некоторой величины зачастую дкя простоты изложения заменяется термином "ожидаемое значение", например "глкилаемое время работы алгоритма" означает "математическое ожидание времени работы алгоритмат — Примеч.

ред. Глава 2. Приступаем к изучению 5! ван метод вероятностного анализа, применяемый в книге к ряду алгоритмов. Однако область его использования ограничена, поскольку не всегда очевидно, какие входные данные для данной задачи являются "усредненными". Часто делается предположение, что все наборы входных параметров одного и того же обьема встречаются с одинаковой вероятностью.