分而治之递归算法的复杂性

Question

我正在尝试获取特定分治算法的复杂性，因此转置给定矩阵。

根据我一直在阅读的内容，我知道递归应该如下开始：

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

我知道如何解决递归问题，但我不确定它是否正确。每次调用该函数时，问题都会除以 2（vars 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;
        }
    }
}

我真的被递归和分而治之的复杂性困住了。我不知道如何继续。

Answer 1

每个递归步骤都会将元素数量减少 4 倍，因此递归级别的数量将是 O(log n) 的阶数。在每个级别，交换的顺序为 O(n^2)，因此算法的复杂度为 O((n^2)(log n)).

Answer 2

你搞错了递归。它是 4C(n/2) + O(n²)，因为当将矩阵返回时，对于大小 n，总共有 n²个元素。

两种方式：

Master Theorem

这里有 a = 4, b = 2, c = 2, Log_ba = 2

因为，Log_ba == c，这属于情况2，导致复杂度为O(n^c log n) = O(n² log n).

循环树可视化

如果您尝试展开您的循环，您会发现您正在解决大小为 n 的问题，方法是将其分解为大小为 n/2 的 4 个问题，然后执行大小为 n²（每个级别）。

每个级别完成的总工作量 = 4 * 工作量 (n/2) + n²

级别总数将等于您必须划分 n 个大小的问题的次数，直到您遇到大小为 1 的问题。这将简单地等于 Log₂n.

因此，总的工作量= Log(n) (4*(n / 2) + n²)，也就是O(n²日志 n).

分而治之递归算法的复杂性

Complexity of a divide and conquer recursive algorithm

c

recursion

complexity-theory