递归的时间复杂度你真的懂吗？不是所有的二分递归都是logn级别
本篇文章的书写灵感来源于【代码随想录】，自己写东西纯粹只是给自己看，而且我写的东西估计只有我自己才能看懂，laugh@Hygge。
首先说明一下，在我很长一段时间这样以为，二分递归这一部分的时间复杂度肯定是O（log n)，但是我实在太天真了 🙁
以下通过举例说明说明情况：计算xn的简单题
最容易想到的O（n）算法代码直接略过，将x一个一个依次乘起来，这种方法在面试官看来，简直就是violence。
接下里我们想想还有其他方法吗？比如，万能的缩小时间复杂度的递归，这样会有如下的思路
想到：利用二分进行递归？哇塞，感觉发现了新大陆，please No talking，show me UR code!
1 function (int x, int n){ 2 if (n == 0): 3 return 1 4 if (n % 2 == 1): # 判奇偶性 5 return function(x, n / 2) * function(x, n / 2) & x 6 else: 7 return function(x, n / 2) * function(x, n / 2) 8 }
写出这样的代码，哇塞，天之骄子啊！但是你确定这样的递归缩短了时间复杂度到O（logn）吗？
我么来分析一波！！！
在这里，很容易犯的误区来了，你看这个递归树的深度就是logn，所以说时间复杂度就是logn（感觉理直气壮）！但是首先我来说明第一个误区：递归树的深度不是时间复杂度，时间复杂度计算公式应该是「递归的次数 * 每次递归中的操作次数」，在上图中，仔细想一想，每一个node会执行一次乘法，但是然后自顶向上，计算乘法的次数是23（第4层递归操作次数）+22（第3层递归操作次数）+21（第2层递归操作次数）+20 （第1层递归操作次数）= 24 – 1（顺便记住计算n层满二叉树的公式，以后面试可能会遇到）。最后：我们发现上面代码执行的递归时间复杂度还是O（n）！所以这个递归和violence的时间复杂度还是一样，而且递归反而还要增加一个系统自动维护地递归栈，切线程，非常耗时！
在这里，我们根据算法中主定理(T(n) = aT(n /b) + nd)来解释时间复杂度：T(n)= 2T(n/2) + 1(这个加的1是合起来的一次乘法运算)，根据主定理，a=2,b=2,d=0，a<bd，所以T(n) = nlogba=nlog22=n，综上所述，T(n) = n （That\’s way bad!）
言归正传，那么递归根本没有进行改进呀呀呀，有其他方法改改进吗？哈哈哈哈哈，答案是肯定的，霍纳法则！霍纳法则就是专门解决xn的计算问题滴！
霍纳法则的代码和矩阵快速幂一样，模板如下：
1 ans = 1 2 function (int x, int n){ 3 while n: 4 if n & 1: 5 ans = y * x 6 x = x * x 7 n = n > 1 #n/2 8 }
这个办法没有用到递归，但是时间复杂度分析真正实现了O（logn），congrats{✿✿ヽ(°▽°)ノ✿}！！！
好了，写完了，总结一下：
1.使用递归，时间复杂度绝对不总是O(logn)
2.霍纳法则求n次方问题