分治策略——算法学习（二）
前言
在算法设计的世界中，分治策略（Divide and Conquer）是一种极具魅力的思想，它通过将复杂问题拆解为多个规模较小但结构类似的子问题，从而以递归的方式解决问题。这种策略不仅高效而且直观，为许多经典算法的诞生奠定了基础，如快速排序（Quick Sort）、归并排序（Merge Sort）和二分查找（Binary Search）等。
（本文代码均使用c#语言）
概念
分治策略是一种经典的算法设计范式，核心思想是将一个复杂的问题分解为多个相互独立的较小子问题，分别解决这些子问题，然后将子问题的解合并起来得到原问题的解。
核心步骤
-
分解（Divide）
将原问题分解为若干规模较小、性质与原问题相似的子问题。这些子问题通常是通过递归处理的 -
解决（Conquer）
当子问题足够简单时，直接求解；否则，继续递归分解，直到子问题可以被直接解决。 -
合并（Combine）
将子问题的解按一定规则合并成原问题的解。
适用情况
- 该问题的规模缩小到一定的程度就可以容易地解决
- 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质
- 利用该问题分解出的子问题的解可以合并为该问题的解
- 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题
归并排序
分解待排序的n个元素序列成各具n/2个元素的两个子序列，然后使用归并排序递归地排序两个子序列，最后合并两个已排序的子序列以产生已排序的答案（归并排序不是原址排序）
归并排序伪代码：
//辅助过程
Function merge(A,p,q,r):
n1 <- q - p + 1;
n2 <- r - q;
//分解
//即A[p ,... ,q],R[q+1, ... ,r]
let L[1 ... n1 + 1] and R[1 ... n2 + 1] be new arrays;
for i <- 1 to n1 do
L[i] <- A[p + i - 1];
end
for j <- 1 to n1 do
R[j] <- A[q+j];
end
L[n1 + 1] <- ∞; //哨兵
R[n2 + 1] <- ∞; //哨兵
i <- 1;
j <- 1;
//合并
for k <- p to r do //k所在的位置就是下一个数要插入的位置
if L[i] <= R[j] then
A[k] <- L[i];
i <- i+1;
end
else
A[k] <- R[j];
j <- j+1;
end
end
end
//完整递归
Function merge-sort(A,p,r):
if p < r then
q <- [(p+ r) / 2];
merge-sort(A,p,r); //递归分解左序列，直到只剩一个数
merge-sort(A,q + 1,r); //递归分解右序列，直到只剩一个数
merge(A,p,q,r); //分解完成后每层按照规则排序插入
end
end
例题：求逆序对
求一组数的逆序对（给定一个数组 A[1…n]A[1 \dots n]A[1…n]，如果数组中存在两个下标 i 和 j，满足： i<j，A[i]>A[j]那么，(i，j) 就被称为数组中的一个逆序对）
输入说明
第一行一个整数n(1≤n≤106)，这组数中数字的个数。第二行n个整数，第i个整数ai(1≤ai≤106)表示第i个数（数字可能相同）
输出说明
一个整数，表示逆序对数量
输入样例
5
2 3 8 6 1
输出样例
5
解答
可以使用归并排序对数据进行排序，在合并过程中，原序列的逆序对数量等于两个子序列的逆序对数量加两个子序列之间的逆序对数量，而右边序列每个元素所贡献的逆序对数量等于左边序列中比它大的元素个数。所以子序列元素的顺序不会影响子序列间的逆序对数量，这样我们就可以在归并排序的过程中统计逆序对数量。
完整代码
using System;
class Test {
static int InversionsMerge(int[] A, int p, int q, int r) {
int n1 = q - p + 1;
int n2 = r - q;
int[] L = new int[n1 + 1];
int[] R = new int[n2 + 1];
int i = 0;
int j = 0;
for (i = 0; i < n1; i++) {
L[i] = A[p + i];
}
for (j = 0; j < n2; j++) {
R[j] = A[q + j + 1];
}
L[n1] = int.MaxValue;
R[n2] = int.MaxValue;
i = 0;
j = 0;
int inversions = 0; //定义变量用于统计逆序对
for (int k = p; k <= r; ++k) {
if (L[i] <= R[j]) {
A[k] = L[i];
++i;
}
else {
inversions += n1 - i; //逆序对数量等于左边序列比右边序列元素大的元素个数
A[k] = R[j];
++j;
}
}
return inversions;//返回逆序对数量
}
static int InversionsMergeSort(int[] A, int p, int r) {
if (p >= r) return 0;
int q = (p + r) / 2;
int inversions = 0;
inversions += InversionsMergeSort(A, p, q);//递归中累计逆序对
inversions += InversionsMergeSort(A, q + 1, r);//递归中累计逆序对
inversions += InversionsMerge(A, p, q, r);//递归中累计逆序对
return inversions;//返回最终逆序对数量
}
static void Main() {
int n = int.Parse(Console.ReadLine());
int[] A = new int[n];
string[] inputs = Console.ReadLine().Split(' ');
for (int i = 0; i < n; i++) {
A[i] = int.Parse(inputs[i]);
}
Console.WriteLine(InversionsMergeSort(A, 0, n - 1));
Console.ReadLine();
}
}
分析
- 解空间：
归并排序算法的解空间可以视为一个递归分层的二叉树，每个节点表示一个子问题，这种树的深度为 O(logn)O(\log n)O(logn)，宽度在最底层达到最大，为 n 个叶子节点。 - 时间复杂度：
为了简化分析，假设问题的规模n是2的幂。那么分解需要常量时间D(n)=\(\Theta\)(1); 递归地求解2个规模为n/2的问题需要2T(n/2)的时间； 最后在一个具有n个元素的子数组上运行merge的过程需要\(\Theta\)(n)的时间，所以D(n)=\(\Theta\)(n)。由于使用递归分解，分解过程相当于将问题规模逐步缩小一半，直到子数组的大小为 1，因此，递归分解的层数是 O(logn)。综上，总时间复杂度为O（nlogn）
二分查找
找原序列的中间元素下标mid，将原序列分解为L=(a1,a2,...,amid)和R=(amid+1,amid+2,...,an)两个子序列。若v<=amid则递归地在序列L中查找v，否则递归地在序列R中查找v。若序列只有一个元素则检查唯一的序列元素是否和v相等（无需合并）
伪代码
//递归法
Function binary-search(A,l,r,v):
if l = r then
if A[l] = v then return l;
else return NIL;
end
mid <- [(l+r)/2];
if v <= A[mid] then return binary-search(A,l,mid,v);
else return binary-search(A,mid+1,r,v);
end
//非递归法
Function binary-search(A,v):
l <- 1;
r <- A.length;
while l<r do
mid <- [(l+r)/2];
if v<= A[mid] then r <- mid;
else l <- mid + 1;
end
if A[l] = v then return l;
else return NIL;
end
分析
- 解空间：解空间表现为一个深度为 O(logn)的递归二叉树，表示在每次迭代中如何通过选择中点来缩小搜索区间。
- 时间复杂度：
共分解2个规模为n/2的子问题，但只有1个子问题要解决，且无需合并。分解所需时间为常数\(\Theta\)(1)，由于使用递归实现，所以这个算法总的时间复杂度为O(logn)
快速排序
将数组A[p, ... , r]划分成2个（可能为空）子数组A[p, ... , q-1]和A[q+1, ... , r]使得A[p, ... , q-1]中的每一个元素都小于等于A[q],同时A[q+1, ... , r]中的每一个元素都大于A[q]，计算下标q也是划分过程的一部分。递归调用快速排序，排序子数组A[p, ... , q-1]和A[q+1, ... , r]，不需要合并
快速排序是原址排序，是实际应用中最优秀的排序算法
伪代码：
//分解方法
Function partition(A,p,r):
x <- A[r]; //选定中间值
i <- p - 1; //小区间末位下标
for j <- p to r - 1 do //大区间末位下标，每次扩容1
if A[j] <= x then //下一个数小于中间值，该去小区间
i <- i + 1; //小区间+1
exchange A[i] with A[j]; //将A[j]交换到小区间
end
end
exchange A[i+1] with A[r]; //将中间值放到中间
return i + 1; //返回中间值下标
end
//主过程
Function quicksort(A,p,r):
if(p < r) then
q <- partition(A,p,r);
quicksort(A,p,q-1);
quicksort(A,q+1,r);
end
end
例题：快速排序
使用一种原址排序的方式对一组数据进行从小到大排序
输入说明
第一行一个整数n(1≤n≤106)，表示轻小说的数量。第二行n个用空格分隔的整数，第i个整数ai(−106≤ai≤106)表示第i个数。
输出说明
n个用空格分隔的整数，表示这组数据从小到大排序后的结果。
输入样例
5
9 8 2 5 2
输出样例
2 2 5 8 9
解答
完整代码
using System;
class Test {
static void Main(string[] args) {
// 读取输入的小说数量
int n = int.Parse(Console.ReadLine());
// 读取小说的编号并转换为整数数组
string[] input = Console.ReadLine().Split(' ');
int[] numbers = new int[n];
for (int i = 0; i < n; i++) {
numbers[i] = int.Parse(input[i]);
}
// 快速排序
QuickSort(numbers, 0, n - 1);
foreach (int i in numbers) {
Console.Write(i + " ");
}
Console.ReadLine();
}
// 快速排序方法
static void QuickSort(int[] arr, int left, int right) {
if (left < right) {
int pivotIndex = Partition(arr, left, right);
QuickSort(arr, left, pivotIndex - 1); // 递归排序左半部分
QuickSort(arr, pivotIndex + 1, right); // 递归排序右半部分
}
}
// 分区方法
static int Partition(int[] arr, int left, int right) {
int pivot = arr[right]; // 选择最右边的元素作为基准
int i = left - 1; // i 指向比 pivot 小的区域的尾部
for (int j = left; j < right; j++) {
if (arr[j] <= pivot) // 把小于等于 pivot 的元素放到左边
{
i++;
Swap(arr, i, j);
}
}
// 将 pivot 放到正确的位置
Swap(arr, i + 1, right);
return i + 1;
}
// 交换两个元素
static void Swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
分析
- 解空间：快速排序的解空间即存储空间的复杂度，主要受到递归调用栈深度的影响。因为快速排序是一个就地排序算法（in-place），所以它并不需要额外的空间来存储数据。快速排序的空间复杂度主要来自递归调用的栈空间。在平均情况下，快速排序的递归深度为 O(logn)，因此需要的空间复杂度是：O(logn)
- 时间复杂度：分解过程相当于把所有的n个数都访问了一遍，所以分解的复杂度为\(\Theta\)(n)。主过程采用递归实现，递归的深度为O(logn)，因此平均时间复杂度为O(nlogn)