Fibonacci数列之转移矩阵法

Fibonacci数列： 在讲递归和递推时都是经典例题，一般都是递归(O(2^n))，递推(O(n))，也有用通项公式法
看上去是O(1)，其实不然，我们还应该考虑乘方运算的时间消耗。如不加特别优化，用乘法实现n次乘方的时间复杂度为O(n)。

但是上帝跟我说了一种非常规的算法——转移矩阵法！
这个矩阵的n次方就是 ，即Fibonacci数列的第n项!
如求F5：

然后二分一下，复杂度就变成O(lgn)了！