Теория алгоритмов

Прямой анализ рекурсивного дерева вызовов

  1. Алгоритм сортировки слиянием

    Рассмотрим подход к получению функции трудоемкости рекурсивного алгоритма, основанный на непосредственном подсчете вершин дерева рекурсивных вызовов, на примере алгоритма сортировки слиянием.

    Рекурсивная процедура 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

  2. Слияние отсортированных частей (Merge)

    Рассмотрим процедуру слияния отсортированных частей массива А, использующую дополнительные массивы Bp и Bq, в конец которых с целью остановки движения индекса помещается максимальное значение. Поскольку сам алгоритм рекурсивной сортировки устроен так, что объединяемые части массива А находятся рядом друг с другом, то алгоритм слияния вначале копирует отсортированные части в промежуточные массивы, а затем формирует объединенный массив непосредственно в массиве А.

    Merge (A,p,r,q,Bp,Bq) (В {} взято количество операций в данной строке)

    Max <-- A[r] {2}
    If Max Max <-- A[q] {(1/2)*2}
    kp <-- r - p + 1 {3}
    p1 <-- p – 1 {2}
    For i <-- 1 to kp (копирование первой части) {1+kp*3}
    Bp [ i ] <-- A[p1 + i ] {kp*(4)}
    Bp[ kp+1] <-- Max {3}
    kq <-- q - r {2}
    For i <-- 1 to kq (копирование второй части) {1+ kq*3}
    Bq [ i ] <-- A[ r + i ] {kq*(4)}
    Bq [ kq+ 1] <-- Max {3}
    (заметим, что m=kp + kq = q – p + 1 – длина объединенного массива)
    pp <-- p {1}
    pq <-- r+1 {2}
    For i <-- p to q (слияние частей) {1+m*3}
    If Bp [ pp ] < Bq [ pq ] {m*3}
    Then
    A[ i ] <-- Bp[ pp ] {(1/2)*m*3}
    pp <-- pp +1 {(1/2)*m*2}
    Else
    A [ i ] <-- Bq [ pq ] {(1/2)*m*3}
    pq <-- pq +1 {(1/2)*m*2}
    Return(A)
    End

    На основании указанного количества операций можно получить трудоемкость процедуры слияния отсортированных массивов в среднем:

    (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)

  3. Подсчет вершин в дереве рекурсивных вызовов

    Алгоритм, получая на входе массив из 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 вершин – это вершины в которых рассматривается только один элемент массива, что приводит к останову рекурсии.

  4. Анализ трудоемкости алгоритма сортировка слиянием

    Таким образом, для 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* ) не измениться.

Rambler's Top100
Hosted by uCoz