C语言-斐波那契（Fibonacci）数列三种不同求法时间复杂度分析

深碍√TFBOYSˉ_ 2022-07-13 05:17 101阅读 0赞

**方法一 递归**

提起斐波那契数列，首先想到的大概都是递归，但是其时间复杂度并非最优，其时间复杂度为O(2^N)。具体分析可以参考：[Fibonacci][]

**方法二 循环**

递归之所以效率低下，是因为需要重复的计算一些中间变量。而利用循环可以通过存储中间变量来减小计算量，其时间复杂度为O(N)。

**方法三 矩阵乘法**

利用矩阵乘法加上分治的思想，可以将其时间复杂度降低到O(log2^n).具体的代码如下。关于其思路分析可以参考：[Fibonacci][Fibonacci 1]

#include<stdio.h>
    
    typedef struct MTX{
    	int m00;
    	int m01;
    	int m10;
    	int m11;
    }mtx;
    mtx mtx0;

mtx m_multiply(mtx a, mtx b)
    {
    	mtx c;
    	c.m00=a.m00*b.m00+a.m01*b.m10;
    	c.m01=a.m00*b.m01+a.m01*b.m11;
    	c.m10=a.m10*b.m00+a.m11*b.m10;
    	c.m11=a.m10*b.m01+a.m11*b.m11;
    	return c;
    }
    
    mtx m_power(int k)
    {
    	mtx m;
    	
    	if(1==k)
    	{
    		m=mtx0;
    		return m;
    	}
    	else if(0==k%2)
    	{
    		m=m_multiply(m_power(k/2),m_power(k/2));
    		return m;
    	}
    	else
    	{
    		m=m_multiply(m_power((k-1)/2),m_power((k-1)/2));
    		m=m_multiply(m,mtx0);
    		return m;
    	}
    }
    int fibonacci(int n)
    {
    	int m;
    	mtx mtx1;
    	
    	int t[2]={0, 1};
    	if(n<3)
    		return t[n];
    	else
    		mtx1=m_power(n-2);
    	return mtx1.m00;
    }
    
    int main(void)
    {
    	mtx0.m00=1;
    	mtx0.m01=1;
    	mtx0.m10=1;
    	mtx0.m11=0;
    	int n=8;
    	
    	int m=fibonacci(n);
    	printf("Fibonacci(%d)=%d",n,m);
    	return m;
    }

[Fibonacci]: http://blog.sina.com.cn/s/blog_6ab0b9a80101axdn.html
[Fibonacci 1]: http://blog.csdn.net/xygy8860/article/details/47087687