算法设计与分析学习记录-递归与分治策略_算法设计与分析 对子问题进行二分检索,当子问题规模为1时,直接比较x与t

分治策略的基本思想

• 对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。

 

• 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。

 

• 分治法的设计思想是，将一个难以直接解决的大问题,分割成一些规模较小的相同问题，以便各个击破，分而治之。

 

 注意点：

• 子问题与原始问题性质完全一样
• 子问题之间可彼此独立的求解
• 递归停止时子问题可直接求解

二分检索算法 

 二分检索算法设计思想：

• 通过 x 与中位数的比较，将原问题归结为规模 减半的子问题，如果 x 小于中位数，则子问题 由小于 x 的数构成，否则子问题由大于 x 的数 构成. 
• 对子问题进行二分检索.
• 当子问题规模为 1 时，直接比较 x与 T[m]，若 相等则返回 m，否则返回 0.

二分检索时间复杂度分析： 

 

 二分归并排序

二分归并排序时间复杂度分析： 

 二分归并排序设计思想：

• 将原问题归结为规模为 n/2 的2 个子问题
• 继续划分，将原问题归结为规模为 n/4 的 4 个 子问题. 继续...，当子问题规模为1 时，划分结 束
• 从规模 1到 n/2，陆续归并被排好序的两个子 数组. 每归并一次，数组规模扩大一倍，直到 原始数组 

分治算法的适用条件 

 分治算法的一般性描述

 

设计要点： 

1. 原问题可以划分或者归约为规模较小的子问题
2. 子问题规模足够小时可直接求解
3. 子问题的解综合得到原问题的解
4. 算法实现：递归或迭代 

 

 分治算法时间复杂性分析

 两类常见的递推方程

 

递推方程的求解 

 

 

 分治算法的实例—快速排序

快速排序讲解视频 

伪代码：

划分过程： 

 

划分实例： 

 

时间复杂度

 

 均衡划分的时间复杂度

 

 递归树求解

平均时间复杂度 

 

 

改进分治算法的途径 

• 减少子问题数
• 增加预处理
• 合理设计合并求解算法

减少子问题个数的依据 

大整数乘法问题 

 

 通过减少子问题个数

 

 

 

 

 计算过程图示

 

 

矩阵相乘问题

 

简单分治算法 

 

 

 Strassen 矩阵乘法-减少子问题规模

 

 

 

 

增加预处理 -平面点对问题

蛮力算法 

  一维方法一

 一维分治策略

 

二维分治尝试

划分实例

 

 鸽巢原理的简单应用

 方案一

 

方案二 检查p下方的点

 算法伪代码

 

增加预处理-排序放到分治之前 

 

 递归中的拆分

 

 算法图示

 

 用其中的最小值来定义区域Q

 

 从点3开始逐步往下检查窗口寻找最短距离

 检查点11和点12，距离小于d进行更新

 

 算法代码

预排序 

  输入

 主要程序代码

 

最大子数组

问题背景

问题定义

 

蛮力算法

 

 

 

 

蛮力算法伪代码 

 

 蛮力算法的时间复杂度

 蛮力算法实例分析

 优化枚举-算法实例

 

 

优化枚举伪代码 

 

 优化枚举算法时间复杂度

 分治算法

 合并问题解：求解S3

 

 

时间复杂度

 

 伪代码

 

 

 算法实例

 

 伪代码

 

 

 

 

 时间复杂度

 

 

小结