1.5 KiB
1.5 KiB
算法复杂性分析
- 最优性
- 最坏情况最优
- 平均情况最优
第二章
- 递归
- 递归算法：直接或者间接的调用自身
- 递归函数：用函数自身给出定以的函数
- 阶乘函数
- 边界条件和递归方程是递归函数的两个要素
- Fibonacci 兔子繁殖问题
- 双递归函数：当一个函数以及他的一个变量是由函数自身定义时，无法找到非递归定义
- 避免使用嵌套函数
- 整数划分
- 分治法
- 将一个难以直接解决的大问题，分割成一些规模比较小的相同问题，以便各个击破分而治之
- 分解
- 将一个问题分解为k个子问题，子问题独立且与原问题形式相同
- 求解
- 若子问题规模较小而且容易被解决就直接解，否则递归的解这些子问题
- 合并
- 将各个子问题的解合并得到原问题的解
- 适用条件
- 该问题规模能缩小到一定的程度就可容易的解决
- 可以分解为若干个规模较小的相同问题，该问题具有最优子结构性质
- 该问题分解出的子问题可以合并为该问题的解
- 子问题相互独立，子问题之间不包含相同的子问题
- 用分治法设计算法时最好使子问题的规模大致相同
- 二分法
- 大整数的乘法
- 加减法代替乘法
- 每个矩阵都分成相等4块
- strassen矩阵乘法
- 棋盘覆盖
- 分割成四四份然后没有特殊方块的三份交汇处放一个方框