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