李春葆主笔的《算法分析与设计》第二版中的第三章详解分治法
最编程
2024-07-30 22:28:25
...
分治法的一般步骤
- 分解成若干子问题:将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题
- 求解子问题:若子问题规模较小,容易被解决,则直接求解,否则递归地解各个子问题。
- 合并子问题:将各个子问题地解合并成原问题地解
分治法的一般特征:
分治法所能解决的问题一般具有以下几个特征:
- 该问题的规模缩小到一定程度就可以容易地解决
-
该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质
-
利用该问题分解出的子问题的解,可以合并为该问题的解
-
该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共子问题
排序问题
快速排序(写第一次排序后的顺序):
过程
- 首先选择第一个元素k作为基准划分成两个子问题,左边小于k,右边大于k
- 其次对左右子序列执行相同的操作,若长度为1或0则是有序的返回,否则第一个元素作为基准划分成两个子问题。
划分算法
- 从右往左扫描,若a[j]>=k,则j--,否则a[i]=a[j],即将a[j]放到基准元素k的前面。
- 步骤1否则语句执行后,从左往右扫描 若a[i]<=k,则i++,否则a[j]=a[i],即将a[i]放到基准元素k的后面。
算法时间复杂度O(N)
归并排序:
此算法就是不断地分治,其每一趟也比较好理解。
算法时间复杂度O(log2(n))
中间还有题目不知道是不是重点暂时不复习
求解大整数乘法和矩阵乘法问题:
习题 :
下一篇: 玩转数据结构(第三部分):探讨线性表