4.1选最大与最小
1.选择问题
概念
问题
选最大问题：顺序比较
伪码：
同时选最大最小问题：
通常算法：先选出最大数，再从剩下的n-1个数里选最小数
算法
分组算法：两两数分成一组，每组进行比较，在所有大的数+轮空数里选出最大数，在所有小的数+轮空数里选出最小数
伪码：先分组再比较再选数
最坏情况时间复杂度：
分治算法：递归
最坏情况时间复杂度：
2.小结：
- 选最大：顺序比较，比较次数 n - 1
- 选最大最小：
- 1.选最大+选最小：比较次数 2n - 3
- 2.分组：比较次数 ⌈3n/2⌉ - 2
- 3.分治：n = 2ᵏ 比较次数 3n/2 - 2
4.2选第二大
1.选第二大问题+算法
蛮力算法
顺序比较：
锦标赛算法：用空间换时间
提高效率的途径：
锦标赛算法：
伪码：
实例：
时间复杂度分析
2.小结：
- 常规算法蛮力解决：调用2次找最大：2n - 3
- 锦标赛算法：n + ⌈logn⌉ - 2
- 思路：用空间换时间
4.3一般性选择问题：选第k小的数
1.一般性选择问题
问题
算法
简单的算法：
分治算法：
m*的选择与划分过程：
实例：n = 15,k = 6
归约为子问题：
伪码：
2.小结：
- 选第k小的算法：
- 分治策略
- 确定m*
- 用m*划分分数组归约为子问题
- 递归实现
4.4选择问题的算法分析
1.算法分析
详情
用m*划分：
子问题规模估计：
时间复杂度递推方程：
递归树：W(n) = W(n/5) + W(7n/10) + cn
2.递归调用：
1.求m*的工作量与|M| = n/t 相关，t为每组元素数，t大，|M|小
2.归约后子问题大小与分组元素数t有关，t大，子问题规模大
3.三分组时的子问题规模：假设t=3,3个一组
时间复杂度
算法的时间复杂度：
4.小结：
- 选第k小算法的时间分析：
- 递推方程
- 分组时每组元素数的多少对时间复杂度的影响
4.5卷积及应用
1.卷积的定义
向量定义&矩阵解释
定义：
矩阵理解：
实例：
2.卷积与多项式乘法的关系
详情
3.卷积的应用：信号平滑处理
详情
实例：两边有误差
4.小结：
- 卷积的定义
- 卷积与多项式乘法的关系
- 卷积的应用--信号平滑处理
4.6卷积计算
1.蛮力算法
详情
卷积a*b计算等价于多项式相乘
蛮力算法的时间：O(n²)
2.多项式 高斯滤波
详情
计算2n-1次多项式C(x):
高斯滤波的权值函数:
2n个数的选择：1的2n次根:
实例：
快速傅里叶变换FFT
算法
3.小结：
- 蛮力算法O(n²)
- 快速傅里叶变换FFT算法：
- 确定x的取值：1的2n次根
- 关键步骤：多项式对x求值
4.7多项式求值算法
1.蛮力算法
详情
2.改进的求值算法
详情
偶系数与奇系数多项式
分治求值算法设计
3.FFT算法
详情
伪码：
时间复杂度：
4.小结：
- 多项式求值算法：
- 蛮力算法：O(n³)
- 改进的求值算法：O(n²)
- FFT算法：O(nlogn)
4.8平面点集的凸包
1.平面点集的凸包
问题
分治算法
伪码：
算法分析--时间复杂度
2.小结：
- 平面点集的凸包是分治算法的一种应用