算法分析与设计复习__递归方程与分治

总结自：【算法设计与分析】期末考试突击课_哔哩哔哩_bilibili

1.递归，递归方程

1.1递归条件:

1.一个问题的解可以分解为几个子问题的解；

2.这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样;

3.存在递归终止条件。

1.2递归方程的建立，求解

1.2.1建立

当算法包含调用自身的过程时，其运行时间可用递归方程描述，

下面是递归方程建立的具体过程:假设问题规模为"，T(m)为解决该问题的时间开销。

1.2.2求解

常用的求解递归方程的方法有两种:替换方法和主定理

1.2.2.1替换方法

用替换方法解某个递归方程时，分为两步。
首先是猜测问题解的某个界限，然后用数学归纳法证明所猜测解的正确性。猜测问题的界限可以根据经验猜，也可以把递归方程逐项展开，再对项进行合并根据合并结果猜测问题的界限。

1.2.2.2主定理（较简单，套公式即可）

1.2.2.3主定理不能解决的部分：

1.2.3例题

斐波那契序列，欧几里得算法，汉诺塔，阶乘；

1.2.3.1替换方法例题:

1.2.3.2主定理例题:

1.2.3.3 参考答案

T1:

T2:

T3:

T4:

T5:

T6:

T7:

1.3 分治法

分治法的思想：