chap3 分治
快速排序算法的最坏情况时间复杂度
1）概述
快速排序算法的最坏情况时间复杂度是 O(n²)。
最坏情况出现在以下条件下：
- 当输入数组已经完全排序（升序或降序）
- 每次都选择最小或最大的元素作为基准
在这种情况下，每次划分后的两个子数组极度不平衡：
- 一个子数组包含n-1个元素
- 另一个子数组为空
递归调用的深度变为n，而每一层的比较操作是O(n)，因此总时间复杂度为： O(n) × O(n) = O(n²)
2）实例
在快速排序的最坏情况下（例如数组已经排序，且每次都选择最小或最大元素作为基准），递归过程会形成这样的结构：
假设输入数组为[1,2,3,4,5]，每次选择第一个元素作为基准：
第1次递归：
- 选择1作为基准
- 分区后：[] 和 [2,3,4,5]
- 需要递归处理[2,3,4,5]
第2次递归：
- 选择2作为基准
- 分区后：[] 和 [3,4,5]
- 需要递归处理[3,4,5]
第3次递归：
- 选择3作为基准
- 分区后：[] 和 [4,5]
- 需要递归处理[4,5]
第4次递归：
- 选择4作为基准
- 分区后：[] 和 [5]
- 需要递归处理[5]
第5次递归：
- 选择5作为基准，数组只有一个元素，递归结束
两个关键点：
递归调用的深度变为n：
- 对于长度为n的数组，需要递归调用n次才能完成排序
- 每次递归只能处理掉一个元素（基准元素）
每一层的比较操作是O(n)：
- 在每一层递归中，需要将基准与剩余的每个元素进行比较
- 第一层需要n-1次比较，第二层需要n-2次比较，…
- 总的比较次数接近：(n-1) + (n-2) + … + 1 ≈ n²/2，即O(n)级别
因此，最坏情况下的总时间复杂度为：递归深度O(n) × 每层操作O(n) = O(n²)
快速排序的平均情况时间复杂度（p156）
首先，分析基于以下 假设 ：所有元素都是不同的，且每个元素作为基准（pivot）的概率相同。
step1 建立递归关系
这里引入了函数C(n)表示对n个元素进行快速排序的平均比较次数：
- 选择基准元素需要0次比较
- 将其他元素与基准比较需要(n-1)次比较
- 递归部分的成本取决于划分后两个子数组的大小
如果选择第w个元素作为基准（w从1到n），得到大小为(w-1)和(n-w)的两个子数组。那么递归处理这两个子数组的比较次数为C(w-1)和C(n-w)。
考虑基准元素的随机性，任何元素被选为基准的概率是1/n，因此有：
C(n) = (n-1) + (1/n)∑[从w=1到n](C(w-1) + C(n-w))
step2 简化递归式
关键观察是：∑[从w=1到n]C(n-w) = ∑[从w=1到n]C(w-1)
这两个求和是等价的，因为C(n-w)展开为C(n-1) + C(n-2) + … + C(0)，而C(w-1)展开为C(0) + C(1) + … + C(n-1)，它们只是顺序不同。
于是递归式简化为： C(n) = (n-1) + (2/n)∑[从w=1到n]C(w-1)
step3 消除递归依赖
这个递归式依赖于所有历史值C(n-1), C(n-2), …, C(0)，很难直接求解。解决方法是：
将等式两边乘以n： nC(n) = n(n-1) + 2∑[从w=1到n]C(w-1)
用n-1替换n得到： (n-1)C(n-1) = (n-1)(n-2) + 2∑[从w=1到n-1]C(w-1)
从第一个等式减去第二个等式，并整理： C(n)/(n+1) = C(n-1)/n + 2(n-1)/(n(n+1))
step4 引入新变量简化
引入D(n) = C(n)/(n+1)，将上述等式重写为： D(n) = D(n-1) + 2(n-1)/(n(n+1))，其中D(1) = 0
step5 求解D(n)
D(n) = 2∑[j=1到n]/(j(j+1))
通过数学变换和部分分式分解： (j-1)/(j(j+1)) = 2/(j+1) - 1/j
进一步计算得出： D(n) = 2ln n - Θ(1) ≈ 2(log n)/log e ≈ 1.44log n
step6 最终结果
C(n) = (n+1)D(n) ≈ 1.44n log n
这证明了快速排序的平均时间复杂度为O(n log n).
MUTISELECT多选算法
1）问题定义
- 给定一个数组A[1…n]，包含n个不同元素
- 给定一个已排序的数组K[1…r]，包含r个从1到n的整数（表示排名）
- 目标：找出A中排名为K[i]的元素，对所有1≤i≤r
2）算法思路
中间排名选择：
- 找出K数组的中间排名k = K[⌈r/2⌉]
- 使用SELECT算法（如快速选择算法）找出A中第k小的元素a
划分：
- 将A分成两个子序列：
- A₁：所有小于a的元素
- A₂：所有大于a的元素
- 将A分成两个子序列：
调整排名：
- 对于K₁ = ⟨k₁, k₂, …, k[⌈r/2⌉-1]⟩（小于中间排名的排名）
- 对于K₂ = ⟨k[⌈r/2⌉+1] - k, k[⌈r/2⌉+2] - k, …, k_r - k⟩（大于中间排名的排名，需要调整）
- 注意在K₂中，排名需要减去k，因为已经找出了k个较小的元素
递归：
- 递归调用MULTISELECT(A₁, K₁)
- 递归调用MULTISELECT(A₂, K₂)
3）算法实例
- 数组A = [42, 15, 20, 8, 35, 27, 17, 10]（8个元素）
- 排名数组K = [2, 5, 7]（我们想找第2小、第5小和第7小的元素）
第一次调用MULTISELECT(A, K)：
找中间排名：
- r = 3，所以⌈r/2⌉ = 2
- 中间排名k = K[2] = 5（我们要找第5小的元素）
执行SELECT找第5小元素(SELECT算法的时间复杂度是O(n))：
- 使用SELECT算法找到A中第5小的元素，这里是27
- 所以a = 27
划分A（通过把A数组的所有元素依次比较来划分,所以这一步的时间复杂度是O(n)）:
- A₁ = [15, 20, 8, 17, 10]（所有小于27的元素）
- A₂ = [42, 35]（所有大于27的元素）
分割K：
- K₁ = [2]（小于中间排名5的排名）
- K₂ = [7-5] = [2]（大于中间排名5的排名，需要调整，因为已经找到了5个较小元素）
递归调用：
- MULTISELECT(A₁, K₁)：在[15, 20, 8, 17, 10]中找第2小的元素
- MULTISELECT(A₂, K₂)：在[42, 35]中找第2小的元素
递归调用MULTISELECT(A₁, K₁)：
找中间排名：
- r = 1，所以⌈r/2⌉ = 1
- 中间排名k = K₁[1] = 2
执行SELECT找第2小元素：
- 在A₁中找第2小的元素，这里是10
- 返回10作为原数组A的第2小元素
递归调用MULTISELECT(A₂, K₂)：
找中间排名：
- r = 1，所以⌈r/2⌉ = 1
- 中间排名k = K₂[1] = 2
执行SELECT找第2小元素：
- 在A₂中找第2小的元素，这里是42
- 返回42作为原数组A的第(5+2)=7小元素
最终结果：
- 第2小的元素是10
- 第5小的元素是27（在第一次划分时已确定）
- 第7小的元素是42
这个例子展示了MULTISELECT算法如何通过分治策略高效地找出多个特定排名的元素，而不需要对整个数组进行完全排序。每次找到中间排名的元素后，问题被分解为两个更小的子问题，大大减少了计算量。
MULTISELECT时间复杂度分析
1）算法的关键步骤
- 选择中间排名元素（使用SELECT算法）
- 对数组进行划分
- 递归处理两个子问题
令T(n,r)表示对包含n个元素的数组，找出r个排名对应元素的时间复杂度（r为k数组长度）。
2）SELECT算法的复杂度
首先，调用的SELECT算法（即查找第k小元素的算法）的时间复杂度为O(n)。
3）划分的复杂度
数组划分需要O(n)时间，将所有元素与基准元素比较一次。
4）递归调用的复杂度
递归调用分为两部分：
- MULTISELECT(A₁, K₁)，其中A₁包含约n/2个元素（在平均情况下），K₁包含⌈r/2⌉-1个排名
- MULTISELECT(A₂, K₂)，其中A₂包含约n/2个元素（在平均情况下），K₂包含r-⌈r/2⌉个排名
5）递归方程
在平均情况下，我们可以写出如下递归方程：
$T(n,r) = O(n) + T(n/2, r/2) + T(n/2, r/2)$
简化为：
$T(n,r) = O(n) + 2T(n/2, r/2)$
6）分析递归方程
与标准分治算法不同，这里我们有两个变量n和r。让我们考虑几种情况：
当r = 1时：
- 问题退化为标准SELECT，复杂度为O(n)
当r = n时：
- 递归树高度为$log n$
- 每层总工作量为$O(n)$
- 相当于完整排序，总复杂度为$O(n log n)$
当1 < r < n时 (一般情况)：
- 在递归深度为i的层次，有$2^i$个子问题（递归过程可以用一棵满二叉树表示）
- 每个子问题的规模约为$n/2^i$和$r/2^i$
- 每层的总复杂度为O(n)
- 递归深度为$log r$ (当$r/2^i$变为1时停止）
- 因此总体复杂度为$O(n log r)$
7）最终复杂度
MULTISELECT算法的时间复杂度为 O(n log r).
大整数乘法：时间复杂度分析
对于两个n位的大整数u和v，将它们各自分为两部分：
- u = w·2^(n/2) + x （高位部分w和低位部分x）
- v = y·2^(n/2) + z （高位部分y和低位部分z）
最初的计算方法需要4次乘法：
- $uv = (w·2^(n/2) + x)(y·2^(n/2) + z)$
- $uv = wy·2^n + (wz + xy)·2^(n/2) + xz$
这里需要计算wy, wz, xy和xz四次乘法。
使用一个巧妙的技巧，引入等式：
- $wz + xy = (w + x)(y + z) - wy - xz$
这样，我们可以不直接计算wz和xy，而是：
- 计算(w + x)(y + z)
- 使用已经需要计算的wy和xz
- 通过减法得到wz + xy
这样就把乘法次数从4次减少到3次：
- wy（高位部分相乘）
- xz（低位部分相乘）
- (w + x)(y + z)（中间项的辅助计算）
最终的计算公式为：
- $uv = wy·2^n + [(w + x)(y + z) - wy - xz]·2^(n/2) + xz$
这种优化将时间复杂度从传统的O(n²)（对于n位数的乘法）改进为约O(n^log₂3)≈O(n^1.585)，当处理非常大的整数时，这种差异会变得非常显著。
递归关系T(n)表示计算n位数乘法所需的时间，其中：
- 如果n=1，需要常数时间d
- 如果n>1，需要3个大小为n/2的乘法，外加一些线性时间bn的加减操作
最近点对问题
1）思路
划分：用一条垂直线x=L划分左右点集，在左右点集中分别找到最小距离![[截屏2025-03-15 16.40.07.png 500]] 合并：但是最小点距离并不一定是在左半区域$S_l$或右半区域$S_r$中的其中一个，也可能是这样：在x=L的左边有一个点，右边有一个点，这两个点的距离才是最小的
设$δ=min (δ_1,δ_2)$，其中$δ_1,δ_2$分别是左右半边的最小点距，那么如果存在上面所说的“跨中线”的最短点对，那么这两个点之间的距离一定小于δ，所以它们横坐标的差至少是δ，所以我们可以把视野缩小到这样一个strip条形：
![[截屏2025-03-15 16.47.20.png|200]]还可以进一步缩小检索区域：对于每个点p，上一步确定了我们只需要比较它与y坐标在[p.y, p.y+d]范围内的点的距离。更妙的是，可以证明每个点最多只需要比较其后的7个点(具体证明略,方法是用圆形面积来证)，于是阴影区域T的每个点最多只需要和T中的7个点进行比较。
2）时间复杂度分析
见书 P105～P106
为什么使用MERGESORT能将复杂度降低到$O(nlogn)$？
优化在于，当递归返回时，我们可以在O(n)时间内通过mergesort的合并操作（而非重新排序），将$Y_l$和$Y_r$合并为按y坐标排序的完整数组Y；
- 为什么在合并时要排序？
- 排序是必要的，因为算法的效率依赖于一个关键性质：对于每个点，我们只需要检查y坐标差小于d的点。如果点按y坐标排序，就可以限制每个点最多检查7个其他点；
- 如果不排序，就需要对strip中的每对点都计算距离，这将是O(n²)的操作，会使整个算法效率更低；
- 传统算法的缺陷
在标准的分治算法中，合并步骤的流程如下：- 将点集P按x坐标分为左半部分S_l和右半部分S_r
递归地找出S_l和S_r各自的最近点对，得到最小距离d = min(d_l, d_r)
处理跨越中线的情况：
找出所有x坐标在[x_mid-d, x_mid+d]范围内的点，形成一个子集合strip
==对strip中的点按y坐标排序==
比较每个点与其后有限个点的距离，可能更新d
问题就出在”==对strip中的点按y坐标排序==”这个排序操作。在朴素实现中，我们在每次递归调用时都会重新对strip进行完整的排序，这是一个O(n log n)的操作；而当我们用mergesort替代这个朴素的排序后，这个排序步骤的时间复杂度就能优化为O(n)；