Анализ трудоемкости алгоритма сортировка слиянием
Таким образом, для 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* ) не изменится.
Дата добавления: 2018-02-28; просмотров: 768; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!