斐波那契数列
斐波那契数列通项公式
$F(n) = \frac{\sqrt{5}}{5}((\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n)$
斐波那契数列时间复杂度
递归缺点
大量的重复计算
递归改进
- 递归转递推
- 递归转记忆化递归(带备忘录的递归)
时间复杂度
递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归中的操作次数。
举例：求$x$的$n$次方 想一下这么简单的一道题目，代码应该如何写呢。 最直观的方式应该就是，一个for循环求出结果，代码如下：
int function1(int x, int n) {
int result = 1; // 注意 任何数的0次方等于1
for (int i = 0; i < n; i++) {
result = result * x;
}
return result;
}
时间复杂度为$O(n)$，有没有效率更好的算法呢。
那么就可以写出了如下这样的一个递归的算法，使用递归解决了这个问题。
int function(int x, int n) {
if (n == 0) {
return 1;
}
return function(x, n - 1) * x;
}
那么这个代码的时间复杂度是多少？
一些同学可能一看到递归就想到了O(logn)，其实并不是这样，递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归中的操作次数。
那再来看代码，这里递归了几次呢？
每次$n-1$，递归了$n$次时间复杂度是$O(n)$，每次进行了一个乘法操作，乘法操作的时间复杂度一个常数项$O(1)$，所以这份代码的时间复杂度是 $n * 1 = O(n)$。
这个时间复杂度还是太高,于是又写出了如下的递归算法的代码：
int function(int x, int n) {
if (n == 0) {
return 1;
}
if (n % 2 == 1) {
return function(x, n / 2) * function(x, n / 2) * x;
}
return function(x, n / 2) * function(x, n / 2);
}
这份代码的时间复杂度又是多少呢？
我们来分析一下，首先看递归了多少次呢，可以把递归抽象出一颗满二叉树。刚刚同学写的这个算法，可以用一颗满二叉树来表示（为了方便表示，选择$n$为偶数$16$），如图：
当前这颗二叉树就是求$x$的$n$次方，$n$为$16$的情况，$n$为$16$的时候，进行了多少次乘法运算呢？
这棵树上每一个节点就代表着一次递归并进行了一次相乘操作，所以进行了多少次递归的话，就是看这棵树上有多少个节点。
熟悉二叉树话应该知道如何求满二叉树节点数量，这颗满二叉树的节点数量就是 $2^3 + 2^2 + 2^1 + 2^0 = 15$，可以发现：这其实是等比数列的求和公式，这个结论在二叉树相关的面试题里也经常出现。
这么如果是求$x$的$n$次方，这个递归树有多少个节点呢，如下图所示：($m$为深度，从$0$开始)
时间复杂度忽略掉常数项$-1$之后，这个递归算法的时间复杂度依然是$O(n)$。对，你没看错，依然是$O(n)$的时间复杂度！
这个递归的算法依然还是$O(n)$啊。
那么$O(logn)$的递归算法应该怎么写呢？
想一想刚刚给出的那份递归算法的代码，是不是有哪里比较冗余呢，其实有重复计算的部分，于是又写出如下递归算法的代码：
int function(int x, int n) {
if (n == 0) {
return 1;
}
int t = function(x, n / 2);
if (n % 2 == 1) {
return t * t * x;
}
return t * t;
}
再来看一下现在这份代码时间复杂度是多少呢？
依然还是看他递归了多少次，可以看到这里仅仅有一个递归调用，且每次都是 $n/2$ ，所以这里我们一共调用了$log$以$2$为底$n$的对数次。
每次递归了做都是一次乘法操作，这也是一个常数项的操作，那么这个递归算法的时间复杂度才是真正的$O(logn)$。
二叉树性质
二叉树的五种遍历
前序遍历：根-左-右 中序遍历：左-根-右 后序遍历：左-右-根
推导 前序 + 中序 => 后续 后续 + 中序 => 前序 前序 + 后续 不唯一解
一：二叉树的前序遍历：根-左-右 先遍历根节点，然后 先遍历完 左子树，最后遍历右子树；在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树 前序遍历 = 深搜 前序遍历结果：ABDECF（第一个是根节点）
二：二叉树的中序遍历：左-根-右 先遍历完左子树，然后遍历根节点，最后遍历右子树；在遍历左、右子树时，仍然先遍历左子树，然后遍历根节点，最后遍历右子树； 中序遍历结果：DBEAFC
三：二叉树的后序遍历：左-右-根 先遍历完左子树，然后再遍历完右子树，最后遍历根节点；在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根节点 后序遍历结果：DEBFCA（最后一个一定是根节点）
四：二叉树的深度优先搜索
从 root 开始，一条路走到底，然后再退回到上一个节点，然后再走下一条路，直到所有节点都遍历完；
遍历顺序如下：
五：二叉树的宽度优先遍历（层次遍历）
从 root 开始遍历，先遍历这个节点的相邻节点，然后再依次遍历相邻节点的相邻节点，也就是层序遍历
宽搜的顺序与序号相同
—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com
