3.1分治算法的设计思想
1.分治策略
基本思想&实例
基本思想:
实例一:二分检索
算法&设计思想&时间复杂度
算法:
设计思想:
时间复杂度:
实例二:二分归并排序
算法&设计思想&时间复杂度
算法:
设计思想:
时间复杂度:
实例三:Hanoi塔的递归算法
算法&设计思想
算法:
设计思想:
2.小结:
- 子问题与原问题具有相同的性质
- 子问题规模足够小时可直接求解
- 算法可以递归也可以迭代实现
- 算法的分析方法: 递推方程
3.2分治算法的一般描述和分析方法
详情
一般描述:
时间分析:
两类常见的递推方程:
求解方法:
方程1:迭代法、递归树
方程2:迭代法、换元法、递归树、主定理
小结:
- 分治算法的一般描述:
- 划分或规约为彼此的子问题
- 分别求解每个子问题
- 给出递归或迭代计算的终止条件
- 如何由子问题的解得到原问题解
- 分治算法的分析方法:
- 求解时间复杂度的递推方程
- 常用的递推方程的解
3.3芯片测试
1.测试过程&分析:
详情
测试结果分析:
问题:
判定芯片A的好坏:
2.蛮力算法&分治算法
详情
蛮力算法:
分治算法设计思想:
分治算法的正确性:
n为奇数时的特殊处理:
伪码描述:
时间复杂度分析:
3.小结:
- 保证子问题与原问题性质相同:增加额外处理
- 额外处理的工作量不改变函数的阶
- 时间复杂度为O(n)
3.4快速排序
1.分治策略:
详情
基本思想:
伪码:
划分过程:
划分实例:
时间复杂度:
2.小结:
- 分治策略
- 子问题划分是由首元素决定
- 最坏情况下时间O(n^2)
- 平均情况下时间为O(nlogn)
3.5幂乘算法及应用
1.幂乘问题:
详情
分治算法--划分:
2.应用:
详情
算法:
3.小结:
- 分治算法的例子--幂乘算法
- 幂乘算法的应用
- 计算Fibonacci数
- 通常算法O(n),分治算法为O(logn)
分治算法改进:
