Шпаргалка по "Теории Алгоритмов"

{if (a[pos1] < a[pos2]) 
temp[pos3++] = a[pos1++]; 
else 
temp[pos3++] = a[pos2++];}// одна последовательность закончилась - // копировать остаток другой в конец буфера  
while (pos2 <= ub) // пока вторая последовательность непуста  
temp[pos3++] = a[pos2++]; 
while (pos1 <= split) // пока первая последовательность непуста 
temp[pos3++] = a[pos1++];// скопировать буфер temp в a[lb]...a[ub] 
for (pos3 = 0; pos3 < ub-lb+1; p

18.Анализ временной сложности рекурсивных алгоритмов. Сортировка Хоара.

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

Временну́ю сложность  алгоритма выражают функцией Т(n) зависимости времени работы (числа элементарных действий) от размера входа. Размер входа определяется для каждой задачи индивидуально. Обычно у задачи есть какой-нибудь естественный параметр, характеризующий объем входных данных, и сложность оценивается по отношению к этому параметру.

Проведем анализ временной  сложности быстрой сортировки

(сортировки Хоара).

Основная процедура сортировки имеет вид:

Procedure QuickSort(l, r : Integer);

Var x, i, j : Integer;

Begin

If l<r Then Begin

  x:=A[(l+r) Div 2]; {выбор значения барьерного элемента}

  i:=l; r:=j;

  Repeat  {перестановка  элементов: слева от барьерного  – элементы, меньшие его, а справа

– большие}

   While (A[i]<x) Do Inc(i);

   While (A[j]>x) Do Dec(j);

   If i<=j Do Begin

    Swap(A[i], A[j]);

    Inc(i); Dec(j)

   End

  Until i>j;                    Действия на входе в рекурсию

QuickSort(l, j); {рекурсивный вызов для левой части}

  QuickSort(i, r); {рекурсивный  вызов для правой части}                            Два рекурсивных вызова

 End

End;

Время перестановки элементов  в рассматриваемой части пропорционально  длине этой части, т. е. в общем  виде для части из n элементов D(n) = Θ(n). Действий на выходе из рекурсии алгоритмом не предусмотрено, т. е. время соединения полученных решений S(n) = Θ(1). В процедуре присутствует два рекурсивных вызова, для выполнения аналогичных действий для двух полученных в результате перестановки элементов частей массива (не обязательно равной длины), т. е. T(n1) и T(n2). Заметим, что n2 ≈ n–n1.  Если в массиве один элемент, то происходит выход из процедуры сразу после проверки условия (l<r), т. е. T(1) = Θ(1). Таким образом, получили рекуррентное соотношение вида:

Таким образом, получили рекуррентное соотношение вида:

.

В общем случае n₂=n–n₁.

Упростим данное рекуррентное соотношение с учетом свойств  асимптотических обозначений:

.

Решить данное рекуррентное соотношение рассмотренными выше методами не удается, так как в соотношении  присутствует формально введенный  параметр n₁. Для того чтобы «избавиться» от него, рассмотрим работу алгоритма в лучшем и в худшем случаях.

Лучший случай

Характеризуется делением рассматриваемой  части массива при каждом рекурсивном  вызове пополам. Таким образом, n₁=n/2, n-n₁=n/2, и рекуррентное соотношение с учетом свойств асимптотических обозначений принимает вид:

.

Таким образом, получено рекуррентное соотношение, аналогичное  рекуррентному соотношению сортировки слиянием, т. е.  
T_{лучший случай}(n)=O(n·log₂n).

Худший случай

Худший случай для времени работы алгоритма характеризуется выбором  в качестве барьерного элемента при каждом рекурсивном вызове максимального (или минимального) элемента рассматриваемой части. Тогда сортируемое множество элементов каждый раз разбивается на две части таким образом, что в одной части оказывается один элемент, а в другой – все остальные. Таким образом, n₁=1, n-n₁=n-1, и рекуррентное соотношение с учетом свойств асимптотических обозначений принимает вид:

.