Рассмотрим подход к получению функции трудоемкости рекурсивного алгоритма, основанный на непосредственном подсчете вершин дерева рекурсивных вызовов, на примере алгоритма сортировки слиянием.
Рекурсивная процедура Merge Sort – MS получает на вход массив А и два индекса p и q, указывающие на ту часть массива, которая будет сортироваться при данном вызове. Вспомогательные массивы Bp и Bq используются для слияния отсортированных частей массива.
MS(A, p ,q, Bp, Bq)
If pq (проверка останов рекурсии при p=q)
then
r<--(p+q) div
2
MS(A, p, r, Bp,Bq) (рекурсивный вызов для первой части)
MS(A, r+1, q,
Bp,Bq) (рекурсивный вызов для второй части)
Merge(A, p, r, q, Bp, Bq)
(слияние отсортированных частей)
Return (A)
End
Рассмотрим процедуру слияния отсортированных частей массива А, использующую дополнительные массивы Bp и Bq, в конец которых с целью остановки движения индекса помещается максимальное значение. Поскольку сам алгоритм рекурсивной сортировки устроен так, что объединяемые части массива А находятся рядом друг с другом, то алгоритм слияния вначале копирует отсортированные части в промежуточные массивы, а затем формирует объединенный массив непосредственно в массиве А.
Merge (A,p,r,q,Bp,Bq) (В {} взято количество операций в данной строке)
На основании указанного количества операций можно получить трудоемкость процедуры слияния отсортированных массивов в среднем:
(m) =
2+2+1+3+2+1+kp*7+3+2+1+kq*7+3+1+2+1+m*(3+3+3+2) = 11*m + 7*(kp+kq) + 23 =
18*m+23. (10.1)
Алгоритм, получая на входе массив из n элементов, делит его пополам при
первом вызове, поэтому рассмотрим случай, когда n=, k =
В этом случае мы имеем полное дерево рекурсивных вызовов глубиной k, содержащее n листьев, фрагмент дерева показан на рис 10.1.
Рис 10.1 Фрагмент рекурсивного дерева при сортировке слиянием
Обозначим количество вершин дерева через V:
V = n + n/2+n/4+n/8+...+1 =
n*(1+1/2+1/4+1/8+...+1)=2n - 1= - 1
Из них все внутренние вершины порождают рекурсию, количество таких вершин – Vr = n-1, остальные n вершин – это вершины в которых рассматривается только один элемент массива, что приводит к останову рекурсии.
Таким образом, для n листьев дерева выполняется вызов процедуры MS c
вычислением r+1, проверка условия p=q и возврат в вызывающую процедуру для
слияния, что в сумме с учетом трудоемкости вызова даёт:
F1(n) = n*2*(5+4+1)
+ n*2(If p=q и r+1) = 22*n;
Для n-1 рекурсивных вершин выполняется проверка длины переданного массива,
вычисление середины массива, рекурсивный вызов процедур MS, и возврат,
поскольку трудоемкость вызова считается при входе в процедуру, то мы получаем:
Fr(n) = (n-1)*2*(5+4+1) + (n-1)*(1+3+1) = 24*n - 24;
Процедура слияния отсортированных массивов будет вызвана n-1 раз, при этом
трудоемкость складывается из трудоемкости вызова и собственной трудоемкости
процедуры Merge:
Трудоемкость вызова составит (для 6 параметров и 4-х
регистров):
Fm<вызов>(n) = (n-1)*2*(6+4+1) = 22*n - 22;
Поскольку трудоемкость процедуры слияния для массива длиной m составляет
18*m + 23 (10.1), и процедура вызывается n-1 раз с длинами массива равными n,
n/2, n/4, …, причем 2 раза с длиной n/2, 4 раза с длиной n/4, то со-вокупно
имеем:
Fm<слияние>(n) = (n-1)*23 + 18*n + 2*18*(n/2) + 4*18*(n/4) + …
+ =
= {учитывая, что таким образом обрабатывается k-1 уровней}
= 18*n
*( – 1) + 23*(n-1) = 18*n*
+ 5*n - 23;
Учитывая все компоненты функции трудоемкости, получаем окончательную
оценку:
Fa(n) = F1(n) + Fr(n) + Fm<вызов>(n) + Fm<слияние>(n) =
= 22*n + 24*n - 24 + 22*n - 22 +18*n* + 5*n - 23 =
= 18*n* + 73*n - 69 (10.2)
Если количество чисел на входе алгоритма не равно степени двойки, то
необходимо проводить более глубокий анализ, основанный на изучении поведения
рекурсивного дерева, однако при любых ситуациях с данными оценка главного
порядка Q( n* ) не
измениться.