5.3.1 Алгоритм сортировки Insertion Sort

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

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

Время работы алгоритма для того или иного ввода измеряется в количе­стве элементарных операций, или "шагов", которые необходимо выполнить. Здесь удобно ввести понятие шага, чтобы рассуждения были как можно более машиннонезависимыми. На данном этапе мы будем исходить из точки зрения, согласно ко­торой для выполнения каждой строки псеводкода требуется фиксированное время. Время выполнения различных строк может отличаться, но мы предположим, что одна и та жеi-я строка выполняется за времяc_i, гдеc_i- константа.

В последующих рассуждениях формула для выражения времени работы алго­ритма Insertion_Sort, которая сначала будет сложным образом зависеть от всех величинc_i, значительно упростится благодаря более лаконичным обозначениям, с которыми проще работать. Эти более простые обозначения позволят легче опре­делить, какой из двух алгоритмов эффективнее.

Начнем с того, что введем для процедуры INSERTION_SORTвремя выполнения каждой инструкции и количество их повторений. Для каждогоj = 2,3,..., п, гдеn=length [А], обозначим черезt_j количество проверок условия в циклеwhile(строка 5). При нормальном завершении цикловforилиwhile(т.е. когда перестает выполняться условие, заданное в заголовке цикла) условие проверяется на один раз больше, чем выполняется тело цикла. Само собой разумеется, мы считаем, что комментарии не являются исполняемыми инструкциями, поэтому они не увеличивают время работы алгоритма:c_i

Время работы алгоритма — это сумма промежутков времени, необходимых для выполнения каждой входящей в его состав исполняемой инструкции. Если выполнение инструкции длится в течение времени c_i и она повторяется в алгоритмеп раз, то ее вклад в полное время работы алгоритма равноc_i n. Чтобы вычислить время работы алгоритмаlNSERTION_SORT(обозначим его черезТ (n)), нужно про­суммировать произведения значений, стоящих в столбцахвремя иколичество раз, в результате чего получим:

(5.1)

Даже если размер входных данных является фиксированной величиной, время работы алгоритма может зависеть от степени упорядоченности сортируемых ве­личин, которой они обладали до ввода. Например, самый благоприятный случай для алгоритма INSERTION_Sort — это когда все элементы массива уже отсортиро­ваны. Тогда для каждогоj = 2,3,...,nполучается, чтоА[i]key в строке 5, еще когдаi равно своему начальному значениюj — 1. Таким образом, приj = = 2,3,...,nt_j = 1, и время работы алгоритма в самом благоприятном случае вычисляется так:

T(n)=c₁n+c₂(n-1)+c₄(n-1)+c₅(n-1)+c₈(n-1)=(c₁+c₂+c₄+c₅+c₈)n-(c₂+c₄+c₅+c₈) (5.2)

Это время работы можно записать как an +b, гдеа иb —константы, зависящие от величинc_i ;т.е. это время являетсялинейной функцией отп.

Если элементы массива отсортированы в порядке, обратном требуемому (в дан­ном случае в порядке убывания), то это наихудший случай. Каждый элемент A [j] необходимо сравнивать со всеми элементами уже отсортированного подмноже­стваA [1..j— 1], так что дляj = =2,3,...,nзначенияt_j = j. С учетом того, что

(как выполняется это суммирование, показано в приложении А), получаем, что время работы алгоритма lNSERTJON_SORT в худшем случае определяется соотно­шением

(5.3)

Это время работы можно записать как an² + bn + с, где константы а,b и с зависят от с_i. Таким образом, этоквадратичная функция отп.

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

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

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

• Характер поведения "усредненного" времени работы часто ничем не луч­ше поведения времени работы для наихудшего случая. Предположим, что последовательность, к которой применяется сортировка методом вставок, сформирована случайным образом. Сколько времени понадобится, чтобы определить, в какое место подмассива A[1..j — 1] следует поместить эле­ментА [j]? В среднем половина элементов подмассиваA [1..J— 1] меньше, чемА [j], а половина — больше его. Таким образом, в среднем нужно прове­рить половину элементов подмассиваA[1..j — 1] , поэтомуt_j приблизитель­но равноj/2. В результате получается, что среднее время работы алгоритма является квадратичной функцией от количества входных элементов, т.е. ха­рактер этой зависимости такой же, как и для времени работы в наихудшем случае. В некоторых частных случаях нас будет интересоватьсреднее время рабо­ты алгоритма, или егоматематическое ожидание.