Анализ алгоритмов

Сортировка вставками

Сортировка вставками (insertion sort) удобна для сортировки коротких по­следовательностей. Именно таким способом обычно сортируют карты: держа в левой руке уже упорядоченные карты и взяв правой рукой очередную карту, мы вставляем её в нужное место, сравнивая с имеющимися и идя справа налево (рис. 1.1).

Запишем этот алгоритм в виде процедуры Insertion-Sort, параметром которой является массив А[1..п] (последовательность длины n, подлежащая сортировке). Мы обозначаем число элементов в массиве А через length[A]. Последовательность сортируется «на

Рис. 1. Работа процедуры Insertion-Sort для входа А = (5,2,4,6,1,3). Позиция j пока­зана жирными числами.

месте», без дополнительной памяти (in place): помимо массива мы используем лишь фиксированное число ячеек памяти. После выполнения процедуры Insertion-Sort массив А упорядочен по возрастанию.

1 for (j=2;j<=n;j++){

2 key=A[j];

3 i=j-1;

4 while (i>0 && A[i]>key){

5 A[i+1]=A[i];

6 i=i-1;

7 }

8 A[i+1]=key;

9 }

На рис. 1.2 показана работа алгоритма при А = (5,2,4,6,1,3). Участок A[1.. j-1] составляют уже отсортированные карты, a A[j + 1..n] — ещё не просмотренные. В цикле for индекс j пробегает массив слева направо. Мы берём элемент A[j] (строка 2 алгоритма) и сдвигаем идущие перед ним и большие его по величине элементы (начиная с (j-1)-го) вправо, освобождая место для взято­го элемента (строки 3-6). В строке 8 элемент A[j] помещается на освобождённое место.

Анализ алгоритмов

Рассматривая различные алгоритмы решения одной и той же задачи, по­лезно проанализировать, сколько вычислительных ресурсов они требуют (время работы, память), и выбрать наиболее эффективный. Конечно, надо договориться о том, какая модель вычислений используется. В качестве модели используется обычная однопроцессорная машина с произвольным доступом (random-access machine, RAM), не предусматривающая параллельного выполнения операций.

Сортировка вставками: анализ.Время сортировки вставками зависит от размера сортируемого массива: чем больше массив, тем больше может потребоваться времени. Обычно изучают зависимости времени работы от размера входа. (Впрочем, для алгоритма сорти­ровки вставками важен не только размер массива, но и порядок его элементов: если массив почти упорядочен, то времени требуется меньше.)

Как измерять размер входа (input size)? Это зависит от конкретной задачи. В одних случаях размером разумно считать число элементов на входе (сорти­ровка, преобразование Фурье). В других более естественно считать размером общее число битов, необходимое для представления всех входных данных. Иног­да размер входа измеряется не одним числом, а несколькими (например, число вершин и число рёбер графа).

Временем работы (running time) алгоритма мы называем число элементар­ных шагов, которые он выполняет — вопрос только в том, что считать эле­ментарным шагом. Мы будем полагать, что одна строка псевдокода требует не более чем фиксированного числа операций (если только это не словесное описание каких-то сложных действий — типа «отсортировать все точки по x-координате»). Мы будем различать также вызов (call) процедуры (на который уходит фиксированное число операций) и её исполнение (execution), которое может быть долгим.

Итак, вернёмся к процедуре Insertion-Sort и отметим около каждой стро­ки её стоимость (число операций) и число раз, которое эта строка исполняется. Для каждого j от 2 до n (здесь n = length[A] — размер массива) подсчитаем, сколько раз будет исполнена строка 4, и обозначим это число через t_j. (Заме­тим, что строки внутри цикла выполняются на один раз меньше, чем проверка, поскольку последняя проверка выводит из цикла.)

Insertion-Sort(A) стоимость число раз

1 for(j=2;j<=n;j++){ c₁ n

2 key=A[j]; c₂ n-1

3 i=j-1; c₃ n-1

4 while (i>0 && A[i]>key){ c₄ ∑_j=2ⁿt_j

5 A[i+1]=A[i]; c₅ ∑_j=2ⁿ(t_j-1)

6 i=i-1; c₆ ∑_j=2ⁿ(t_j-1)

7 }

8 A[i+1]=key; c₈ n-1

9 }

Строка стоимостью с, повторённая m раз, даёт вклад cm в общее число опе­раций. (Для количества использованной памяти этого сказать нельзя!) Сложив вклады всех строк, получим

T(n)=c₁n+c₂(n-1) +c₃(n-1)+c₄∑_j=2ⁿt_j+c₅∑_j=2ⁿ(t_j-1)+c₆∑_j=2ⁿ(t_j-1)+c₈(n-1)

Как мы уже говорили, время работы процедуры зависит не только от n, но и от того, какой именно массив размера n подан ей на вход. Для процедуры Insertion-Sort наиболее благоприятен случай, когда массив уже отсортиро­ван. Тогда цикл в строке 4 завершается после первой же проверки (поскольку А[i]≤key при i=j-1), так что все t_j равны 1, и общее время есть

T(n)=c₁n+c₂(n-1) +c₃(n-1)+c₄(n-1) +c₈(n-1)= (c₁+с₂+с₃+с₄+ с₈)n - (с₂+с₃+с₄+ с₈).

Таким образом, в наиболее благоприятном случае время Т(n), необходимое для сортировки массива размера га, является линейной функцией (linear function) от n, т.е. имеет вид Т(n) = аn-b для некоторых констант а и b. (Эти константы определяются выбранными значениями с₁,...,с₈.)

Если же массив расположен в обратном (убывающем) порядке, время работы процедуры будет максимальным: каждый элемент A[j] придётся сравнить со всеми элементами А[1],..., A[j-1]. При этом t_j=j. Поскольку

∑_j=2ⁿj=n(n+1)/2-1, ∑_j=2ⁿ(j-1)=n(n-1)/2,

получаем, что в худшем случае время работы процедуры равно

Т(п)=с₁+с₂(п-1) +с₃(п-1) + с₄ (n(n+1)/2-1)+c₅+c₆)(n(n-1)/2)+c₈(n-1)= 0.5(c₄+c₅+c₆)n²+(c₁+c₂+c₃+0.5(c₄-c₅-c₆+c₈)n-(c₂+c₃+c₄+c₈).

Теперь функция Т(n) — квадратичная (quadratic function), т.е. имеет вид Т(п)=an² + bn + с. (Константы а, b и c здесь также определяются значениями c₁, ... ,с₈.)