算法设计与分析：分治算法

发表于 更新于 分类于

分治算法

例题

大整数乘法

大整数：超过计算机能直接表示和处理的整数

设 XX 和 YY 为大整数，均为 n 未。

XX 可二进制拆分为两部分，前 0 ~ n/2 位为 A，n/2 + 1 ~ n 位为 B。YY 同理拆为 C 和 D 两部分。

故：

\begin{eqnarray*} X &=& A \times 2^{n/2} + B\\ Y &=& C \times 2^{n/2} + D\\ XY &=& (A \times 2^{n/2} + B)(C \times 2^{n/2} + D)\\ &=& AC\times2^n+AD\times2^{n/2}+BC\times2^{n/2}+BD\\ &=& AC\times2^n+(AD+BC)\times2^{n/2}+BD \end{eqnarray*}

需要进行 4 次 2n/22^{n/2} 位乘法 ACAC; ADAD; BCBC; BDBD，以及 2 次移位（×2k\times 2^k 可用移位达成）、3 次加法操作。

得到时间复杂度的计算公式：

T(n)={O(1)n=14T(n/2)+O(n)n>1T(n)=\left\{ \begin{array}{rcl} O(1) & & {n = 1}\\ 4T(n/2)+O(n) & & {n > 1}\\ \end{array} \right.

时间复杂度计算：

\begin{eqnarray*} T(n) &=& 4T(n/2) + O(n)\\ &=& 4(4T(n/4)+ O (n/2))+O(n)\\ &=& 4(4(4T(n/8)+O(n/4)) + O (n/2))+O(n)\\ &&...\\ &=& 4^{\log{n}}O(1) \\ &=& n^2O(1)\\ &=& O(n^2) \end{eqnarray*}

与使用竖式乘法的时间复杂度一样，但是 XY=AC×2n+(AD+BC)×2n/2+BDXY = AC\times 2^n+(AD+BC)\times 2^{n/2} + BD 可以进行变形减少乘法次数，将 $ (AD+BC) $ 变形为 (A−B)(D−C)+BD+AC(A-B)(D-C)+BD+AC，乍一看乘法从原来的 2 次变为了 3 次，但是 ACAC ; BDBD 在其他项中也有出现，所以实际上是将 2 次乘法变成了 1 次乘法，整条式子变成了 3 次乘法，故：

T(n)={O(1)n=13T(n/2)+O(n)n>1T(n)=\left\{ \begin{array}{rcl} O(1) & & {n = 1}\\ 3T(n/2)+O(n) & & {n > 1}\\ \end{array} \right.

计算后得到：

\begin{eqnarray*} T(n) &=& 3T(n/2) + O(n)\\ &=& 3(3T(n/4)+ O (n/2))+O(n)\\ &=& 3(3(3T(n/8)+O(n/4)) + O (n/2))+O(n)\\ &&...\\ &=& 3^{\log{n}}O(1) \\ &=& O(3^{\log{n}})\\ &=& O(n^{\log3}) \end{eqnarray*}

时间复杂度得到改进。

快速排序

递归加分治的经典排序算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int Partition(vector<int> &arr, int start_index, int end_index) {
    int left_index = start_index, right_index = end_index + 1;
    
    while(true) {
        // 从左往右找比基准大的数
        while (arr[++left_index] < arr[start_index] && left_index <= end_index);
        // 从右往左找比基准大的数，这里不需要判断 right_index 是否小于 start_index，因为经过位于开头的基准时会退出循环
        while (arr[--right_index] > arr[start_index]);
        // 找到后比较左右搜索范围是否重合
        if (right_index <= left_index) break;
        // 不重合则交换
        swap(arr[left_index], arr[right_index]);
    }

    // 从 while 循环可以得知，right_index 的右边的数均大于 p，right_index 指向的数总是小于等于 p 的，所以 right_index 所在的位置为基准的位置；
    swap(arr[right_index], arr[start_index]);

    return right_index;
}

void QuickSort (vector<int> &arr, int start_index, int end_index) {
    if (start_index < end_index) {
        int p = Partition(arr, start_index, end_index);
        // 基准之左元素继续划分，这里基准已经位于它正确的位置上了，所以无需对其进行排序
        QuickSort(arr, start_index, p-1);
        // 基准之右元素继续划分
        QuickSort(arr, p + 1, end_index);
    }
}

随机基准划分：期望获得较为对称的划分。

Partition 函数不变，在外包裹一层函数，用于将随机基准与队首元素互换。QuickSort 函数调用该外层函数进行划分即可。

1
2
3
4
5
int RandomPartition(vector<int> &arr, int start_index, int end_index) {
    int rand_index= rand() % (end_index - start_index + 1) + start_index;
    swap(arr[start_index], arr[rand_index]);
    return Partition(arr, start_index, end_index);
}

随机选择算法（选择最 k 小的元素）

在快速排序的 Partition 函数的基础上，划分后的数组基准之右的元素均大于基准之左的元素，若左边的元素数量小于 k，则代表目标数一定在右边的元素中，反之则在左边的元素中，并以此选择一边继续划分，直至左边的长度为 k - 1 为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int RandomSelect(vector<int> &arr, int start_index, int end_index, int k) {
    int partition_index = RandomPartition(arr, start_index, end_index);
    // 这里不应该 + 1，因为左边的长度不包括这个基准
    int left_length = partition_index - start_index;
    // 如果基准正好是第 k 个，那这个基准就是我们要找的值
    if (left_length == k - 1) return arr[partition_index];
    if (left_length >= k) {
        // 左边的长度大于k，要找的元素在左边
        return RandomSelect(arr, start_index, partition_index, k);
    }
    else {
        // 这里 k 要减去左边的长度（包括基准），因为已经剔除了这 left_length + 1个比我们要找的数还小的数
        return RandomSelect(arr, partition_index + 1, end_index, k - left_length + 1);
    }
}