斐波那契 O(logn)时间复杂度的实现---矩阵计算

之前我写过一个递归的实现和 一个通过循环+两个存储 f1, f2 来实现
但是这两个的时间复杂度分别为O(n^2)和O(n)（希望没错）
而一道期末题目是要求我们实现一个O（log n）时间复杂度的斐波那契
于是我们需要用到一个新的算法----矩阵计算

这里有一个比较详细的介绍链接，我就不再多说了
(https://blog.csdn.net/lanchunhui/article/details/80953084)
我主要是想对时间复杂度进行证明，如果有什么错误，希望您指出，证明如下：至于代码，我认为最关键的就是：

		int fib(n){
			...
			int f1,f2;
			if(1==n/2)//这样写容易避免出现错误的赋值=
				{
				f1 = fib(n/2+1);
				f2 = fib(n/2);
				return f1*f1+f2*f2;}
			else{
					f1 = fib(n/2);
					f2 = fib(n/2-1);
					return f1*(f1+2*f2);
			}
		}

好啦，分享到此结束，如果有错误，希望您指出。