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

分治算法

例题

大整数乘法

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

设 $X$ 和 $Y$ 为大整数，均为 n 未。

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

故：

$$\begin{array}{rcl}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\times 2^n+AD\times 2^{n/2}+BC\times 2^{n/2}+BD\\ & =& AC\times 2^n+(AD+BC)\times 2^{n/2}+BD\end{array}$$

需要进行 4 次 $2^{n/2}$ 位乘法 $AC$; $AD$; $BC$; $BD$，以及 2 次移位（$\times 2^k$ 可用移位达成）、3 次加法操作。

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

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

时间复杂度计算：

$$\begin{array}{rcl}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^{2}O(1)\\ & =& O(n^2)\end{array}$$

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

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

计算后得到：

$$\begin{array}{rcl}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^{\log 3})\end{array}$$

时间复杂度得到改进。

快速排序

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

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 函数调用该外层函数进行划分即可。

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 为止。

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);
    }
}