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

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

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

---

两种方式:

1. Master Theorem

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

   因为，Log_ba == c，这属于情况 2，导致 O(n^cLog n) = O(n< sup>2 登录 n).

---

1. 循环树可视化

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

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

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

   因此，总工作量 = Log(n) (4*(n/2) + n²)，即 O(n² Log n)。