算法分顺序和递归，顺序的算法时间复杂度我就不多讲，一般的懂大O计数法的都明白，本次着重讲讲递归
搞懂算法时间复杂度是一个普通程序员和优秀程序员的分水岭，毕竟写出O(lgn)和O(n!)的时间复杂度的区别特别大
先来看letcode一道题，
泰波那契序列 Tn 定义如下：
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
示例 1：
输入：n = 4
输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
示例 2：
输入：n = 25
输出：1389537
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-th-tribonacci-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这是一道经典面试题，属于斐波那契数的升级版，很多人很快的写出算法
/** * @param {number} n * @return {number} */ const tribonacci = (n) => { if (n === 0) { return 0; } else if (n === 1) { return 1; } else if (n === 2) { return 1; } return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3); };
当然这道试题这样写会超时，原因就不细说了，这个时候面试官会问你这么写的算法时间复杂度是多少
有的同学可能一看到递归就想到了logn，其实并不是这样,问他是怎么算的，他好像并不知道
递归树求解
来看一下这道面试题：求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 function2(int x, int n) { if (n == 0) { return 1; // return 1 同样是因为0次方是等于1的 } return function2(x, n - 1) * x; }
面试官问：那么这份代码的时间复杂度是多少？
有的同学可能一看到递归就想到了logn，其实并不是这样
递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归中的操作次数
那我们再来看代码，我们递归了几次呢。
每次n-1，递归了n次 时间复杂度是O(n)，每次进行了一个乘法操作，乘法操作的时间复杂度一个常数项O(1)
所以这份代码的时间复杂度是 n * 1 = O(n)
这个时间复杂度可能就没有达到面试官的预期。
于是同学又写出了这样的一个递归的算法的代码如下 ，来求 x的n次方
int function3(int x, int n) { if (n == 0) { return 1; } if (n % 2 == 1) { return function3(x, n/2) * function3(x, n/2)*x; } return function3(x, n/2) * function3(x, n/2); }
面试官看到后微微一笑，问这份代码的时间复杂度又是多少呢？
我们来分析一下
首先看递归了多少次呢，可以把递归的次数 抽象出一颗满二叉树。
我们刚刚写的这个算法，可以用一颗满二叉树来表示（为了方便表示 我选择n为偶数），如图：
821631635714_.pic862×704 41.1 KB
当前这颗二叉树就是求x的n次方，n为16的情况
n为16的时候 我们进行了多少次乘法运算呢
这棵树上每一个节点就代表着一次递归并进行了一次相乘操作
所以 进行了多少次递归的话，就是看这棵树上有多少个节点。
熟悉二叉树的同学应该知道如何求满二叉树节点数量
这颗满二叉树的节点数量就是2^3 + 2^2 + 2^1 + 2^0 = 15
有同学就会发现 这其实是等比数列的求和公式， 如果不理解的同学可以直接记下来这个结论。
这个结论在二叉树相关的面试题里也经常出现。
这么如果是求x的n次方，这个递归树有多少个节点呢，如下图所示
时间复杂度忽略掉常数项-1之后，我们发现这个递归算法的时间复杂度依然是O(n)。
此时面试官就会问， 貌似这个递归的算法依然还是O(n)啊， 很明显没有达到面试官的预期
那么在思考一下 O(logn)的递归算法应该怎么写
这里在提示一下 上面刚刚给出的那份递归算法的代码，是不是有哪里比较冗余呢。
来看这份优化后的递归算法代码
int function4(int x, int n) { if (n == 0) { return 1; } int t = function4(x, n/2);// 这里相对于function3，是把这个递归操作抽取出来 if (n % 2 == 1) { return t*t*x; } return t*t; }
那我们看一下 时间复杂度是多少
依然还是看他递归了多少次
我们可以看到 这里仅仅有一个递归调用，且每次都是 n/2
所以这里我们一共调用了 log以2为底n的对数次
每次递归了做都是一次乘法操作，这也是一个常数项的操作，
所以说这个递归算法的时间复杂度才是真正的O(logn)。
如果同学们最后写出了这样的代码并且时间复杂度分析的非常清晰，相信面试官是比较满意的。
最后希望通过这么一个简单的面试题，让大家真正了解了递归算法的时间复杂度该如何分析。
主定理
介绍一个叫主定理的东西，这个定理为什么重要，就是因为这个主定理的话，其实它是用来解决所有递归的函数，怎么来计算它的时间复杂度。主定理本身的话，数学上来证明相对比较复杂（关于主定理可以参考维基百科：https://zh.wikipedia.org/wiki…）
也就是说，任何一个分治或者递归的函数，都可以算出它的时间复杂度，怎么算就是通过这个主定理。本身比较复杂的话，那怎样化简为实际可用的办法，其实关键就是这四种，一般记住就可以了
一般在各种递归的情形的话，有上边这四种情形，是在面试和平时工作中会用上
二分查找(Binary search)：一般发生在一个数列本身有序的时候，要在有序的数列中找到目标数，所以它每次都一分为二，只查一边，这样的话，最后它的时间复杂度是O(logn)
二叉树遍历(Binary tree traversal)：如果是二叉树遍历的话，它的时间复杂度为O(n)。因为通过主定理可以知道，它每次要一分为二，但是每次一分为二之后，每一边它是相同的时间复杂度。最后它的递推公式就变成了图中T(n)=2T(n/2)+O(1)这样。最后根据这个主定理就可以推出它的运行时间为O(n)。当然这里也有一个简化的思考方式，就是二叉树的遍历的话，会每一个节点都访问一次，且仅访问一次，所以它的时间复杂度就是O(n)
二维矩阵(Optimal sorted matrix search)：在一个排好序的二维矩阵中进行二分查找，这个时候也是通过主定理可以得出时间复杂度是O(n)，记住就可以了
归并排序(merge sort)：所有排序最优的办法就是nlogn，归并排序的时间复杂度就是O(nlogn)
再附一张主定理的计算方法，目前只找到的比较好的资料
总结：递归可以使用递归树或者主定理去求解，需要多做题去掌握，下次千万不要碰到递归说是O(n)了，如果有问题欢迎指正
