分区概述 (I) ｜ 算法设计与分析

本文正在参加 人工智能创作者扶持计划

本系列分治法重点内容一览：

1. 详解当求解子问题与划分+合并子问题时间复杂度相同时，分治法的整体复杂度
2. 详解最短点对问题为什么可以做到线性的时间复杂度，包括鸽舍原理等。

本系列主要为mooc学习笔记，重点内容为课程未讲解清楚且由笔者独立思考补充之处，如有错误恳请不吝指出。

为什么要学习分治法

使用到分治法求解的问题包括

• 二分查找
• 大整数乘法
• 棋盘覆盖
• 归并排序
• 快速排序
• 线性时间选择
• 最短点对问题
• 循环赛日程表
• 汉诺塔

分治法的设计思想

将一个难以直接求解的大问题,

分解成若干个规模较小的子问题,

递归地求解这些子问题,

然后合并子问题的解得到原问题的解。

注意:

子问题与原问题形式相同

子问题可以彼此独立的求解,

即子问题之间不包含公共的子问题

子问题的规模缩小到一定程度就可以容易地直接求解

分治法的求解过程

划分子问题:

将原问题分解为若干个规模较小,相互独立, 与原问题形式相同的子问题。

求解子问题:

若子问题规模较小而容易被解决则直接求解,

否则递归地求解各个子问题。

合并子问题:

将各个子问题的解合并为原问题的解。

分治法的一般算法描述

Divide_Conquer ( P ) {     
    if ( P的规模足够小 )             
        直接求解P;      
    else
        分解为k个子问题P1, P2, …, Pk;      
        for (i=1; i<=k; i++) {           
            yi = Divide_Conquer(Pi);
        } //递归解决Pi      
    return   Combine(y1, …, yk);  
}

分治法的分析方法

按照递归算法的分析过程,首先建立递归方程,然后求解递归方程

建立递归方程

划分阶段的时间复杂性

• 分解为$a$ 个子问题。

• 每个子问题大小为$n/b$。

• 假设$划分时间=D(n)$

求解子问题阶段的时间复杂性

• $递归调用时间= aT(n/b)$

合并子问题的解阶段的时间复杂性

• 假设$合并时间=C(n)$

递归方程时间复杂度

$\begin{array}{rlr} T(n) & =\Theta(1) & n<c \\ T(n) & =a T(n / b)+D(n)+C(n) & \text { 否则 }\end{array}$

这里的$c$是常数的意思，一般认为如果小于4时，直接求解更快。

然后求解递归方程

$T(n)=\left\{\begin{array}{cc}\Theta(1) & n<c \\ a T(n / b)+f(n) & \text { 否则 }\end{array}\right.$

大小为$n$ 的原问题分成若干个大小为$n/b$的子问题,

其中$a$个子问题需要求解,

而$f(n)$是划分加合并各个子问题的解需要的工作量。即$f(n)=D(n) + C(n)$

分治法总体时间复杂度（‼️‼️）

$T(n)= \begin{cases}O\left(n^{\log _b a}\right) & \Theta\left(n^{\log _b a}\right)>f(n) \\ O\left(n^{\log _b a} \log _2 n\right) & \Theta\left(n^{\log _b a}\right)=f(n) \\ O(f(n)) & \Theta\left(n^{\log _b a}\right)<f(n)\end{cases}$

通过这个时间复杂度公式来看，

当$\text{分解的问题数}b \geq \text{需要求解的子问题} a$时，

会取得比$O(n)$更好的时间复杂度

当$f(n) = O(n^{\log_b a })$时，

递归深度是 $\log_b n$,划分及合并的额外工作的总时间复杂度取决于递归深度，故为 $O(\log_b n)$。

如图所示，分治法中的$b$必然大于等于2且为整数，n必然大于1，故，当$n>1,b>2$时,$\log_b n < \log_2 n$

所以以2为底是时间复杂度的上界，因此我们可以将 $\log_b n$ 写成 $\log_2 n$。

典型分治法：二分法的时间复杂度

二分法的递归方程

$T(n)=2 T(n / 2)+f(n)$

故二分法的时间复杂度如下

$\begin{aligned}& T(n)= \begin{cases}O(n) & \Theta(n)>f(n) \\ O\left(n \log _2 n\right) & \Theta(n)=f(n) \\ O(f(n)) & \Theta(n)<f(n)\end{cases} \end{aligned}$

分治算法的有效性很大程度上依赖于合并步骤的实现效率。

典型分治法实例：归并排序

基本思想:将待排序元素分成大小大致相同的2个子序列,分别对2个子序列进行归并排序,最终将排好序的子序列合并成为所要求的排好序的序列。

其实就是二分法$\begin{aligned} & T(n)=\left\{\begin{array}{cc}O(1) & n \leq 1 \\ 2 T(n / 2)+O(n) & n>1\end{array}\right. \\ & T(n)=O\left(n \log _2 n\right)\end{aligned}$