算法设计与分析Ch04

弃坑了，转战Jeff的《Algorithms》

第四章 分治算法的典型应用

选择问题

输入: 集合 $L$ (含 $n$ 个不等的实数)
输出: $L$ 中第 $i$ 小元素

$i=1$, 称为最小元素
$i=n$, 称为最大元素

位置处在中间的元素, 称为中位元素
$n$ 为奇数, 中位数唯一, $i = (n+1)/2$
$n$ 为偶数, 可指定 $i = n/2+1$

选最大与最小

选最大

顺序比较

选最大最小

通常算法

1. 顺序比较, 先选最大 max
2. 顺序比较, 在剩余数组中选最小 min（类似于选最大算法）

时间复杂性:

$$W(n) = n-1 + n-2 = 2n-3$$

分组算法

分治算法

选第二大

输入: $n$ 个数的数组 $L$
输出: 第二大的数 second

通常算法:

1. 顺序比较找到最大 max
2. 从剩下 $n-1$ 个数中找最大, 即为 second

时间复杂度:

$$W(n) = n-1 + n-2 = 2n-3$$

优化算法的方法

• 成为第二大数的条件：仅在与最大数的比较中被淘汰。
• 要确定第二大数，必须知道最大数。
• 在确定最大数的过程中记录下被最大数直接淘汰的元素。
• 在上述范围(被最大数直接淘汰的数)内的最大数就是第二大数。
• 设计思想：用空间换时间。

锦标赛算法

算法描述

锦标赛算法

1. 两两分组比较，大者进入下一轮，直到剩下 $1$ 个元素 max 为止。
2. 在每次比较中淘汰较小元素，将被淘汰元素记录在淘汰它的元素的链表上。
3. 检查 max 的链表，从中找到最大的元素，即为 second。

伪代码

实例：

时间复杂度

命题：

计算
第一阶段：
元素数: $n$
比较次数: $n-1$
淘汰了 $n-1$ 个元素

第二阶段：
元素数: $\log n$
比较次数: $\log n - 1$
淘汰元素数为 $\log n - 1$

时间复杂度为：

$$\begin{align*} W(n) & = n-1 + \left \lceil \log n \right \rceil -1 \\ & = n + \left \lceil \log n \right \rceil - 2 \end{align*}$$

一般性的选择问题

应用：管道位置

简单算法

算法一:

• 调用 $k$ 次选最小算法
• 时间复杂度为 $O(kn)$

算法二:

• 先排序，然后输出第 $k$ 小的数
• 时间复杂度为 $O(n \log n)$

分治算法

设计思想

实例

伪代码

算法分析

最坏情况时间复杂度

$$\begin{equation*} W(n) \leqslant W(n/5) + W(7n/10) + O(n) \end{equation*}$$

讨论

3 个一组

小结

• 选最大: 顺序比较, 比较次数 $n-1$
• 选最大最小:
  • 选最大+选最小，比较次数 $2n-3$
  • 分组: 比较次数 $\left \lceil 3n/2 \right \rceil -2$
  • 分治: $n=2^k$，比较次数 $3n/2-2$
• 选第二大：
  • 调用 2 次找最大: $2n-3$
  • 采用锦标赛算法: $n + \left \lceil \log n \right \rceil - 2$
    • 主要的技术: 用空间换时间
• 选第 $k$ 小的算法:
  • 分治策略
  • 确定 $m^*$
  • 用 $m^*$ 划分数组，归约为子问题
  • 递归实现
• 选第 $k$ 小算法的时间分析
  • 递推方程
  • 分组时每组元素数量的多少对时间复杂度的影响

信号平滑处理

卷积及其应用

定义

给定向量: $a = (a_0, a_1, \cdots, a_{n-1})$ 和 $b = (b_0, b_1, \cdots, b_{n-1})$
向量和: $a+b = (a_0+b_0, a_1+b_1, \cdots, a_{n-1}+b_{n-1})$
内积: $a·b = a_0b_0 + a_1b_1 + \cdots + a_{n-1}b_{n-1}$
卷积:

$$a*b = (c_0, c_1, \cdots, c_{2n-2}),$$

其中

$$c_k = \sum_{\stackrel{i+j=n }{i,j < n}} a_i b_j , \quad k = 0, 1, \cdots, 2n-2$$

计算实例

卷积的应用

实例

卷积的计算

暴力算法

快速傅里叶变换(FFT)

FFT算法的关键

给定: $x = 1, \omega_1, \omega_2, \cdots, \omega_{2n-1}$，

• 步骤1: 对 $2n$ 个 $x$ 值分别求值得到多项式 $A(x), B(x)$
• 步骤2: 做 $2n$ 次乘法
• 步骤3: 对 $2n$ 个 $x$ 值求多项式 $D(x)$

关键: 一个对所有的 $x$ 快速多项式求值算法

FFT 算法

小结

• 卷积的定义和应用
  • 卷积的定义
  • 卷积与多项式乘法的关系
  • 卷积的应用——信号平滑处理
• 卷积计算
  • 暴力算法 $O(n^2)$
  • 快速傅里叶变换 FFT 算法
    • 确定 $x$ 的取值: 1 的 $2n$ 次根
    • 关键步骤: 多项式对 $x$ 求值
• 多项式求值算法
  • 暴力算法: $O(n^2)$
  • 改进的求值算法: $O(n^2)$
  • FFT算法: $O(n \log n)$
• FFT算法的设计与分析

计算几何——平面点集的凸包

问题背景

分治算法

小结

分治算法的设计

1. 将原问题归约为子问题:
   • 直接划分注意尽量均衡
   • 通过计算归约为特殊的子问题
   • 子问题与原问题具有相同性质
   • 子问题之间独立计算
2. 算法实现:
   • 递归或迭代实现
   • 注意递归执行的边界

分治算法的分析及改进

1. 时间复杂度分析

• 给出关于时间复杂度函数的递推方程和初值
• 求解方程

2. 提高效率的途径

• 减少子问题个数
• 预处理

重要的分治算法

• 检索算法：二分检索
• 排序算法：快速排序、二分归并排序
• 选择算法：选择第 k 小的元素
• 快速傅里叶变换 (FFT)
• 求平面点集的凸包