【算法设计与分析】第四章分治法

╰+哭是因爲堅強的太久メ 2023-07-17 07:00 9阅读 0赞

## 选最大与最小 ##

**一、选择问题**  
输入集合 L (含n个不等的实数)，输出L中第 i 小的元素。  
当i=n时，称为最大元素；  
当i=1时, 称为最小元素；  
位置处在中间的元素，称为中位元素。  
n为奇数，中位数唯一，i = (n+1)/2；  
n为偶数，可指定 i = n/2+1。

**选最大**：顺序比较，先选最大 max。  
算法最坏情况下的时间： W ( n ) = n − 1 W(n)=n-1 W(n)=n−1。  
**选最大最小** ：  
**1）顺序比较**  
先顺序比较选最大 max；在剩余数组中顺序比较选最小min。  
算法最坏情况下的时间： W ( n ) = 2 n − 3 W(n) = 2n-3 W(n)=2n−3  
**2）分组算法**  
将 n 个元素两两一组分成⌊n/2⌋组，每组比较，得到 ⌊n/2⌋ 个较小和 ⌊n/2⌋ 个较大的数；在⌊n/2⌋个较大（含轮空元素）中找最大 max；在⌊n/2⌋个较小（含轮空元素）中 找最小 min。  
算法最坏情况下的时间： W ( n ) = ⌈ 3 n / 2 ⌉ − 2 W(n) = ⌈3n/2⌉-2 W(n)=⌈3n/2⌉−2  
**3）分治算法**  
将数组 L从中间划分为两个子数组 L1 和 L2 9；分别递归地在 L1和L2中求 max1、min1和max2、min2  
max = max\{ max1 , max2\}  
min = min\{ min1 , min2\}  
算法最坏情况下的时间： W ( n ) = ⌈ 3 n / 2 ⌉ − 2 W(n) = ⌈3n/2⌉-2 W(n)=⌈3n/2⌉−2

## 选第二大 ##

**1.顺序比较**  
顺序比较找到最大 max ；从剩下 n -1个数中找最大，就是第二大second  
时间复杂度： W ( n ) = 2 n − 3 W(n) = 2n - 3 W(n)=2n−3  
**2.锦标赛算法**  
两两分组比较，大者进入下一轮，直到剩下 1个元素 max 为止。在每次比较中淘汰较小元素，将被淘汰元素记录在淘汰它的元素的链表上。检查 max 的链表，从中找到最大元，即second。  
1）设参与比较的有 t 个元素，经过i 轮淘汰后元素数至多为⌈t /2i⌉ .  
2）max 在第一阶段分组比较中总计进行了⌈log n⌉次比较.  
时间复杂度是： W ( n ) = n + ⌈ l o g n ⌉ − 2 W(n) = n + ⌈log n⌉ - 2 W(n)=n\+⌈logn⌉−2.

## 选择问题 ##

**一、一般选择问题的算法设计**  
输入数组 S, S 的长度 n, 正整数 k, 1<= k<=n. 输出第 k 小的数.  
1）调用 k 次选最小算法  
时间复杂度为： O ( k n ) O (kn) O(kn)  
2）先排序，然后输出第 k 小的数  
时间复杂度为： O ( n l o g n ) O(nlogn) O(nlogn)  
3）分治算法  
用某个元素 m*作为标准将 S 划分成 S1 与 S2，其中 S1的元素小于 m*，S2 的元素大于等于 m\*。如果 k < |S1|，则在 S1中找第 k 小的数；如果 k = |S1|+1，则 m\*是第 k 小的数；如果 k > |S1|+1，则在 S2中找第k-|S1|-1小的数。

可以将数组分为5个一组，，再每组找出来一个中位数，再在所有的中位数中找出中位数m\* ，以这个数为界限分成两块，再再将不能确定的数注意与m\* 比较，分好组之后，比较小于m\* 一组数个数，与k的关系，译者递归下去，知道找到符合条件的数。  
时间复杂度： W ( n ) = θ ( n l o g n ) W(n)=θ (nlogn) W(n)=θ(nlogn)

## 卷积及其应用 ##

**一、向量计算**  
给定向量：  
a = (a0, a1, …, an-1)  
b = (b0, b1, …, bn-1)  
**向量和**:  a + b = ( a 0 + b 0 , a 1 + b 1 , … , a n − 1 + b n − 1 ) a+b = (a\_0+b\_0, a\_1+b\_1, …, a\_\{n-1\}+b\_\{n-1\}) a\+b=(a0\+b0,a1\+b1,…,an−1\+bn−1)  
**内积** : a ∗ b = a 0 ∗ b 0 + a 1 ∗ b 1 + … + a n − 1 ∗ b n − 1 a\*b = a\_0\*b\_0 + a\_1\*b\_1 + … + a\_\{n-1\}\*b\_\{n-1\} a∗b=a0∗b0\+a1∗b1\+…\+an−1∗bn−1  
**卷积**: a ∗ b = ( c 0 , c 1 , … , c 2 n − 2 ) a\*b = (c\_0, c\_1, …, c\_\{2n-2\}) a∗b=(c0,c1,…,c2n−2),其中 Σ i + j = k ; i , j < n a i ∗ a j , k = 0 , 1 , . . . , 2 n − 2 ; Σ\_\{i+j=k;i,j<n\}a\_i\*a\_j,k=0,1,...,2n-2; Σi\+j=k;i,j<nai∗aj,k=0,1,...,2n−2;

**卷积与多项式乘法**  
多项式乘法：C(x) = A(x) B(x)  
 A ( x ) = a 0 + a 1 x + a 2 x 2 + … + a m − 1 x m − 1 A(x) = a\_0 + a\_1x + a\_2x^2 + … + a\_\{m-1\}x^\{m-1\} A(x)=a0\+a1x\+a2x2\+…\+am−1xm−1  
 B ( x ) = b 0 + b 1 x + b 2 x 2 + … + b n − 1 x n − 1 B(x) = b\_0 + b\_1x + b\_2x^2 + … + b\_\{n-1\}x^\{n-1\} B(x)=b0\+b1x\+b2x2\+…\+bn−1xn−1  
 C ( x ) = a 0 b 0 + ( a 0 b 1 + a 1 b 0 ) x + … + a m − 1 b n − 1 x m + n − 2 C(x) = a\_0b\_0 + (a\_0b\_1+a\_1b\_0) x + … + a\_\{m-1\}b\_\{n-1\} x^\{m+n-2\} C(x)=a0b0\+(a0b1\+a1b0)x\+…\+am−1bn−1xm\+n−2

卷积应用：信号平滑处理

**二、卷积计算**  
**1.蛮力算法**  
向量 a=(a0,a1,…,an-1)和b=(b0,b1,…,bn-1)  
 A ( x ) = a 0 + a 1 x + a 2 x 2 + … + a n − 1 x n − 1 A(x) = a\_0 + a\_1x + a\_2x^2 + … + a\_\{n-1\}x^\{n-1\} A(x)=a0\+a1x\+a2x2\+…\+an−1xn−1  
 B ( x ) = b 0 + b 1 x + b 2 x 2 + … + b n − 1 x n − 1 B(x) = b\_0 + b\_1x + b\_2x^2 + … + b\_\{n-1\}x^\{n-1\} B(x)=b0\+b1x\+b2x2\+…\+bn−1xn−1  
 C ( x ) = a 0 b 0 + ( a 0 b 1 + a 1 b 0 ) x + … + a n − 1 b n − 1 x 2 n − 2 C(x) = a\_0b\_0 + (a\_0b\_1+a\_1b\_0) x + … + a\_\{n-1\}b\_\{n-1\} x^\{2n-2\} C(x)=a0b0\+(a0b1\+a1b0)x\+…\+an−1bn−1x2n−2  
蛮力算法的时间：O (n2)  
**2.快速傅立叶变换FFT**  
1）对  x = 1 , ω 1 , ω 2 , … , ω 2 n − 1 x=1, ω\_1, ω\_2 , … , ω\_\{2n-1\} x=1,ω1,ω2,…,ω2n−1, 分别计算A(x)，B(x)  
2) 利用步1的结果对每个 x = 1 , ω 1 , ω 2 , … , ω 2 n − 1 x=1, ω\_1, ω\_2 , … , ω\_\{2n-1\} x=1,ω1,ω2,…,ω2n−1, 计算C(x)，得到 C ( 1 ) = d 0 , C ( ω 1 ) = d 1 , … , C ( ω 2 n − 1 ) = d 2 n − 1 C(1)=d\_0, C(ω\_1)=d\_1,…,C(ω\_\{2n-1\})=d\_\{2n-1\} C(1)=d0,C(ω1)=d1,…,C(ω2n−1)=d2n−1  
3）构造多项式 D ( x ) = d 0 + d 1 x + d 2 x 2 + … + d 2 n − 1 x 2 n − 1 D(x) = d\_0+d\_1x+d\_2x^2+…+d\_\{2n-1\}x^\{2n-1\} D(x)=d0\+d1x\+d2x2\+…\+d2n−1x2n−1  
4）对 x = 1 , ω 1 , ω 2 , … , ω 2 n − 1 x=1, ω\_1, ω\_2 , … , ω\_\{2n-1\} x=1,ω1,ω2,…,ω2n−1, 计算 D ( x ) , D ( 1 ) , D ( ω 1 ) , … , D ( ω 2 n − 1 ) D(x), D(1), D(ω\_1), … , D(ω\_\{2n-1\}) D(x),D(1),D(ω1),…,D(ω2n−1)

## 快速傅立叶变换:FFT算法 ##

多项式求值算法  
给定多项式：  
 A ( x ) = a 0 + a 1 x + a 2 x 2 + … + a n − 1 x n − 1 A(x) = a\_0 + a\_1x + a\_2x^2 + … + a\_\{n-1\}x^\{n-1\} A(x)=a0\+a1x\+a2x2\+…\+an−1xn−1设 x 为1 的 2n 次方根，对所有的 x 计算 A(x) 的值.  
**1.蛮力法**  
依次计算每个项  a i ∗ x i a\_i\*x^i ai∗xi，i =1, … , n-1 对 a i ∗ x i a\_i\*x^i ai∗xi (i=0,1,…,n-1)求和.  
时间复杂度:  T 1 ( n ) = O ( n 3 ) T1(n) = O(n^3) T1(n)=O(n3)  
**2.改进：**  
依次对 每个 x 做下述计算  
 A 1 ( x ) = a n 1 A1(x)=a\{n\_1\} A1(x)=an1  
 A 2 ( x ) = a n − 2 + x A 1 ( x ) = a n − 2 + a n − 1 x A 3 ( x ) = a n − 3 + x A 2 ( x ) = a n − 3 + a n − 2 x + a n − 1 x 2 A2(x) =a\{n-2\}+xA\_1(x) = a\_\{n-2\}+a\_\{n-1\}x A\_3(x) =a\_\{n-3\}+xA\_2(x) = a\_\{n-3\}+a\_\{n-2\} x+a\_\{n-1\}x^2 A2(x)=an−2\+xA1(x)=an−2\+an−1xA3(x)=an−3\+xA2(x)=an−3\+an−2x\+an−1x2  
……  
 A n ( x ) = a 0 + x A n − 1 ( x ) = A ( x ) A\_n(x) =a\_0+ x A\_\{n-1\}(x) = A(x) An(x)=a0\+xAn−1(x)=A(x)  
时间复杂度 ： T 2 ( n ) = O ( n 2 ) T\_2(n) = O(n^2) T2(n)=O(n2)

**偶系数与奇系数多项式**  
 A ( x ) = A e v e n ( x 2 ) + x A o d d ( x 2 ) A(x) = A\_\{even\}(x\_2) + xA\_\{odd\}(x\_2) A(x)=Aeven(x2)\+xAodd(x2)

**3.分治多项式求值算法**  
一般公式（n为偶数）  
 A ( x ) = a 0 + a 1 x + a 2 x 2 + … + a n − 1 x n − 1 A(x) = a\_0 + a\_1x + a\_2x^2 + … + a\_\{n-1\}x^\{n-1\} A(x)=a0\+a1x\+a2x2\+…\+an−1xn−1  
 A e v e n ( x ) = a 0 + a 2 x + a 4 x 2 + … + a n − 2 x ( n − 2 ) / 2 A\_\{even\}(x)=a\_0+a\_2x+a\_4x^2+…+a\_\{n-2\}x^\{(n-2)/2\} Aeven(x)=a0\+a2x\+a4x2\+…\+an−2x(n−2)/2  
 A o d d ( x ) = a 1 + a 3 x + a 5 x 2 + … + a n − 1 x ( n − 2 ) / 2 A\_\{odd\}(x)=a\_1+a\_3x+a\_5x^2+…+a\_\{n-1\} x^\{(n-2)/2\} Aodd(x)=a1\+a3x\+a5x2\+…\+an−1x(n−2)/2  
 A ( x ) = A e v e n ( x 2 ) + x A o d d ( x 2 ) A(x) = A\_\{even\}(x^2) + xA\_\{odd\}(x^2) A(x)=Aeven(x2)\+xAodd(x2)

时间复杂度： T ( n ) = O ( n l o g n ) T(n)=O(nlogn) T(n)=O(nlogn)

## 平面点集的凸包 ##

问题（平面点集的凸包）  
给定大量离散点的集合Q，求一个最小的凸多边形，使得Q中的点在该多边形内或者边上.

1.  以 连接最大纵坐标点  y m a x y\_\{max\} ymax 和最小纵坐标点  y m i n y\_\{min\} ymin 的线段d=\{  y m a x y\_\{max\} ymax, y m i n y\_\{min\} ymin\}划 分L 为左点集 Lleft 和右点集 Lright
2.   D e a l ( L l e f t ) Deal (L\_\{left\} ) Deal(Lleft)； D e a l ( L r i g h t ) Deal (L\_\{right\} ) Deal(Lright)
3.   D e a l ( L l e f t ) Deal (L\_\{left\} ) Deal(Lleft)：考虑 L l e f t L\_\{left\} Lleft：确定距d最远的点P 在三角形内的点，删除；a 外的点与 a 构成  L l e f t L\_\{left\} Lleft 的子问题;b 外的点与 b 构成  L l e f t L\_\{left\} Lleft 的子问题 .  
     D e a l ( L r i g h t ) Deal (L\_\{right\} ) Deal(Lright)，同理。