Сложность рекурсивного алгоритма разделяй и властвуй - PullRequest
Новая
       13

Сложность рекурсивного алгоритма разделяй и властвуй

1 голос
/ 07 апреля 2019

Я пытаюсь получить сложность конкретного алгоритма «разделяй и властвуй», поэтому транспонирую данную матрицу.

Из того, что я читал, я понял, что рекурсия должна начинаться следующим образом: 

C(1) = 1
C(n) = 4C(n/2) + O(n)

Я знаю, как решить рекурсию, но я не уверен, правильно ли это.Каждый раз, когда вызывается функция, задача делится на 2 (переменные fIni и fEnd), а затем вызываются еще 4 функции.Кроме того, в конце swap вызывается со сложностью O (n²), поэтому я почти уверен, что не учту это в приведенной выше рекурсии.

Код выглядит следующим образом: 

void transposeDyC(int **m,int f,int c, int fIni, int fEnd, int cIni, int cEnd){
    if(fIni < fEnd){
        int fMed = (fIni+fFin)/2;
        int cMed = (cIni+cFin)/2;

        transposeDyC(m,f,c, fIni, fMed, cIni, cMed);
        transposeDyC(m,f,c, fIni, fMed, cMed+1, cEnd);
        transposeDyC(m,f,c, fMed+1, fFin, cIni, cMed);
        transposeDyC(m,f,c, fMed+1, fFin, cMed+1, cEnd);

        swap(m,f,c, fMed+1, cIni, fIni, cMed+1, fEnd-fMed);
    }
}

void swap (int **m,int f, int c,int fIniA, int cIniA, int fIniB, int cIniB, int dimen){
    for (int i=0; i<=dimen-1; i++){
        for (int j=0; j<=dimen-1; j++) {
            int aux = m[fIniA+i][cIniA+j];
            m[fIniA+i][cIniA+j] = m[fIniB+i][cIniB+j];
            m[fIniB+i][cIniB+j] = aux;
        }
    }
}

Я действительно застрял в этой сложности с рекурсией, разделяй и властвуй.Я не знаю, как продолжить.

Ответы [ 2 ]

1 голос
/ 07 апреля 2019

Вы ошиблись в рекурсии. Это 4C (n / 2) + O (n 2 ), потому что при объединении матрицы назад для размера n имеется всего n 2 элементов.

Два способа:

  1. Основная теорема

    Здесь мы имеем a = 4, b = 2, c = 2, Log b a = 2

    Так как, Log b a == c, это подпадает под случай 2, что приводит к сложности O (n c Log n) = O (n 2 Log n).

  1. Визуализация дерева повторений

    Если вы попытаетесь раскрыть свое повторение, вы увидите, что вы решаете проблему размера n, разбив ее на 4 задачи размера n / 2, а затем выполняя работу размера n 2 (на каждом уровне).

    Общее количество выполненных работ на каждом уровне = 4 * Работа (n / 2) + n 2

    Общее количество уровней будет равно количеству раз, которое вам придется разделить на задачу размера n, пока вы не столкнетесь с проблемой размера 1. Это будет просто равно Log 2 n .

    Следовательно, общая работа = Log (n) (4 * (n / 2) + n 2 ), что составляет O (n 2 Log n).

0 голосов
/ 07 апреля 2019

Каждый рекурсивный шаг уменьшает количество элементов в 4 раза, поэтому количество уровней рекурсии будет порядка O (log n). На каждом уровне своп имеет порядок O (n ^ 2), поэтому алгоритм имеет сложность O ((n ^ 2) (log n)).

...