分治策略-典型算法.md

选择问题

选最大和最小

输入:集合LL(含nn个不等的实数)

输出:LL中的第ii小的元素

  • i=1i=1,称为最小元素

  • i=ni=n,称为最大元素

位置处在中间爱你位置的元素,成为中位元素

nn为奇数,中位数唯一,i=(n+1)/2i=(n+1)/2

nn为偶数,可指定为i=n/2+1i=n/2+1

选最大算法:顺序比较,在最坏情况下的时间为W(n)=n1W(n)=n-1

代码为:

1
2
3
4
5
6
7
8
9
10
11
12
def max_value(numbers: List[int]) -> Tuple[int, int]:
if not numbers:
return (-1, -1)
if len(numbers) == 1:
return (0, numbers[0])

m = numbers[0], k = 0
for i in range(1, len(numbers)):
if m < numbers[i]:
m = numbers[i]
k = i
return (k, m)

选最大最小通常算法

  • 比较算法,先选最大max

  • 顺序比较,在剩余数组中选最小min,类似于选最大算法,但比较时保留最小值。

时间复杂度:W(n)=n1+n2=2n3W(n)=n-1 + n-2 = 2n -3

分组算法解决最大最小值

输入:n个数的数组L

输出:max,min

  1. 将n个元素两两一组分成n/2\lfloor n/2 \rfloor组。

  2. 每组比较,得到n/2\lfloor n/2 \rfloor个较小和n/2\lfloor n/2 \rfloor个较大的。

  3. n/2\lceil n/2 \rceil个较大(含轮空元素)找最大max

  4. n/2\lceil n/2 \rceil个比较(含轮空元素)中找最小min

时间复杂度:

  • 在上述代码2中,组内比较n/2\lfloor n/2 \rfloor次。

  • 在3-4行内求max和min比较,最多2×(n/21)2 \times (\lceil n/2 \rceil - 1)次。

  • W(n)=n/2+2×n/22=n+n/22=3n/22W(n)=\lfloor n/2 \rfloor + 2 \times \lceil n/2 \rceil - 2 \\ = n + \lceil n/2 \rceil - 2 \\ = \lceil 3n/2 \rceil -2

分治算法

  1. 将数组LL从中间划分为2个子数组L1,L2L_1, L_2

  2. 递归地在L1L_1中求最大的max1max_1min1min_1

  3. 递归地在L2L_2中求最大的max2max_2min2min_2

  4. maxmax{max1,max2}max \gets \max{\{max_1, max_2\}}

  5. minmin{min1,min2}min \gets \min {\{min_1, min_2\}}

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import math
from typing import List, Tuple


def max_min(arr: List[int]) -> Tuple[int, int]:
i, j = 0, len(arr) - 1
if i == j:
return [arr[i], arr[i]]
elif i == j - 1:
return [arr[i], arr[j]] if arr[i] > arr[j] else [arr[j], arr[i]]
else:
mid = math.floor(j/2)
max1, min1 = max_min(arr[i : mid])
max2, min2 = max_min(arr[mid : j + 1])
return [max(max1, max2), min(min1, min2)]

if __name__ == "__main__":
arr = [6, 10, 32, 8, 19, 20, 222, 14, 53, 1]
max_value, min_value = max_min(arr)
print(max_value, min_value) # 222, 1

最坏情况复杂度:

假设n=2k,W(n)=2W(n/2)+2W(2)=1\quad n=2^k, \\ \quad\quad W(n) = 2W(n/2) + 2 \\ \quad\quad W(2)=1

W(2k)=2W(2k1)+2=2[2W(2k2)+2]+2=22W(2k2)+22+2=...2k1+2k1+...+22+2=3×2k12=3n/22W(2^k) = 2W(2^{k-1}) + 2 \\ = 2 [ 2W(2^{k-2}) + 2] +2 \\ = 2^2W(2^{k-2})+2^2+2=... \\ 2^{k-1} + 2^{k-1} + ... + 2^2 + 2 \\ = 3 \times 2^{k-1} -2 =3n/2-2

选择算法小结

  • 选最大:顺序比较,比较次数n1n-1

  • 选最大最小:

    • 选择最大+最小,比较次数2n32n-3

    • 分组:比较次数3n/22\lceil 3n/2 \rceil -2

    • 分治:n=2kn=2^k,比较次数3n/223n/2-2

选第二大问题

输入:nn个数的数组LL

输出:第二大的数SecondSecond

通常算法:顺序比较

  1. 顺序比较找到最大的maxmax

  2. 从剩下n1n-1个数中找最大,就是第二大的secondsecond

时间复杂度:W(n)=n1+n2=2n3W(n)=n-1+n-2=2n-3 (比较次数)

提高效率的途径

  • 成为第二大数的条件:仅在与最大数的比较中被淘汰

  • 要确定第二大数,必须知道最大数

  • 在确定最大数的过程中被记录下的最大数直接淘汰的元素

  • 在上述范围内(被最大数直接淘汰的数)内最大数就是第二大数

(使用空间换时间)

锦标赛算法

  1. 两两分组比较,大的进入下一轮,直到剩下1个元素maxmax为止;

  2. 在每次比较中淘汰较小的元素,将被淘汰元素记录在淘汰他的元素的链表上。

  3. 检查maxmax的链表,从中找到最大元素,即secodesecode

伪代码:

  1. k <- n // 参与淘汰的元素数字

  2. 将k个元素两两1组,分成k/2\lfloor k/2 \rfloor

  3. 每组的2个数比较,找到较大数

  4. 将被淘汰数记入较大数的链表

  5. 如果 k 为奇数,那么 kk/2+1k \gets \lfloor k/2 \rfloor + 1

  6. 否则 kk/2k\gets \lfloor k/2\rfloor

  7. 如果k>1k>1,那么转到步骤2

  8. max \gets 最大数

  9. second \gets max的链表中最大

其中,1-4是一轮淘汰,7为继续分组淘汰

时间复杂度分析:

命题1 设参与比较的元素有tt个元素,经过ii轮淘汰后元素至多为t/2i\lceil t/2^i \rceil

证 对ii归纳。i=1i=1,分t/2\lfloor t/2 \rfloor,淘汰t/2\lfloor t/2 \rfloor个元素,进入下一轮的元素是tt/2=t/2t - \lfloor t/2 \rfloor = \lceil t/2 \rceil

假设ii轮分组淘汰后元素数至多为t/2i\lceil t/2^i \rceil,那么i+1i+1轮分组淘汰后元素为:

t/2i/2=t/2i+1\lceil \lceil t / 2 ^ i\rceil / 2 \rceil = \lceil t/2^{i+1}\rceil

命题2 maxmax在第一阶段分组比较中总计进行了logn\lceil \log n \rceil次比较。

证 假设到产生maxmax时总计进行kk轮淘汰,根据 命题1n/2k=1\lceil n/2^k \rceil = 1

n=2dn=2^d,那么有k=d=logn=lognk=d=\log {n}=\lceil \log n \rceil

2d<n<2d+12^d<n<2^{d+1} ,那么有k=d+1=lognk=d+1=\lceil \log n \rceil

综上,

  • 第一阶段元素数:nn

    比较次数:n1n-1

    淘汰了n1n-1个元素

  • 第二阶段:元素数logn\lceil \log n \rceil

    比较次数:logn1\lceil \log n \rceil - 1

    淘汰元素数为logn1\lceil \log n \rceil - 1

  • 时间复杂度W(n)=n+logn2W(n)=n + \lceil \log {n} \rceil -2

第二大小结

求第二大算法:

  • 调用2次找最大:2n32n-3

  • 锦标赛算法:用空间换取时间。

一般选择算法的设计

问题:选第k小

输入:数组SSSS的长度nn,正整数k1knk,1\le k\le n

输出:第k小的数

例子

  • S={3,4,8,2,5,9,18},k=4S=\{3, 4, 8, 2, 5, 9, 18\}, k=4,解:5

  • 统计数据的集合SS=nS,|S|=n,选中位数,k=n/2k=\lceil n/2\rceil

选择算法的分析

伪码

算法 Select(S, k)

  1. 将S分成5个一组,共nM=n/5n_M=\lceil n/5 \rceil

  2. 每组排序,中位数防盗集合M

  3. mSelect(M,M/2)m^* \gets Select(M,\lceil M/2 \rceil) // S分A,B,C,D

  4. A,D元素小于 mm^*S1S_1,大于 mm^*S2S_2

  5. S1S1C;S2S2BS_1 \gets S_1 \cup C; \quad S_2 \gets S_2 \cup B

  6. if k=S1+1k=|S_1| + 1 then 输出 mm^*

  7. else if kS1k \le |S_1|

  8. then Select(S1S_1,k)

  9. then Select(S2S_2,k-S1|S_1|-1)

用m*划分

m*划分

n=5(2r+1),A=D=2r\large n=5(2r+1),|A|=|D|=2r

子问题规模至多:2r+2r+3r+2=7r+2\large 2r+2r+3r+2=7r+2

子问题规模估计

不妨设n=5(2r+1)\large n=5(2r+1)A=D=2r\large |A|=|D|=2r

r=n/512=n1012\large r=\frac{n/5-1}{2}=\frac{n}{10}-\frac{1}{2}

划分后子问题规模至多为:

7r+2=7(n1012+2)=7n1032<7n10\large 7r+2=7(\frac{n}{10}-\frac{1}{2}+2) \\ =\frac{7n}{10} - \frac{3}{2} < \frac{7n}{10}

时间复杂度递推方程

算法工作量W(n)W(n)

行2:O(n)O(n) // 每5个数找中位数,构成M

行3:W(n/5)W(n/5) // M中找中位数mm^*

行4:O(n)O(n) // 用mm^*划分集合S

行8-9:W(7n/10)W(7n/10) // 递归

W(n)W(n/5)+W(7n/10)+O(n)\large W(n) \le W(n/5) + W(7n/10) + O(n)

递归树

W(n)W(n/5)+W(7n/10)+O(n)\large W(n) \le W(n/5) + W(7n/10) + O(n)

select_recursion_tree

W(n)cn(1+0.9+0.92+...)=O(n)\large W(n) \le cn(1+0.9+{0.9}^2+...)=O(n)

讨论

为什么使用5个一组,而不是3个一组或者7个一组?

分析:递归调用

  1. mm^*的工作量与M=n/t|M|=n/t相关,tt为每组元素数,tt大,M|M|小。

  2. 归约后子问题大小与分组元素数tt有关,tt大,子问题的规模大。

3分组时的子问题规模

假设t=3t=3,3个一组:

3_per_group

n=3(2r+1)r=(n/31)/2=n/61/2n=3(2r+1) \\ r=(n/3-1)/2=n/6-1/2

子问题规模最多为4r+1=4n/614r+1=4n/6-1

算法时间复杂度

算法时间复杂度满足方程:

W(n)=W(n/3)+W(4n/6)+cnW(n)=W(n/3)+W(4n/6)+cn

由递归树得到W(n)=Θ(nlogn)W(n)=\varTheta (n \log n)

关键点:

  • M|M|与归月后子问题规模值和小于nn

  • 递归树每行的工作量构成公比小于1的等比级数,算法的复杂度才是O(n)O(n)

作者

Hu

发布于

2021-09-07

更新于

2021-08-25

许可协议

评论