3.分治算法的设计思想与分析方法

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)

分治算法改进: