斐波那契数列，时间复杂度为o（log（N））的c++实现
4星 · 超过85%的资源 需积分: 35 163 浏览量
2011-01-03
12:09:33
上传
评论 1
收藏 45KB DOC 举报 
矩阵乘法：
我们将数列写成：
Fibonacci[0] = 0，Fibonacci[1] = 1
Fibonacci[n] = Fibonacci[n-1] + Fibonacci[n-2] (n >= 2)
可以将它写成矩阵乘法形式：
将右边连续的展开就得到：
下面就是要用 O(log(n))的算法计算：
显然用二分法来求，结合一些面向对象的概念，C++代码如下：
class Matrix
{
public:
long matr[2][2];
#
Matrix(const Matrix&rhs);
Matrix(long a, long b, long c, long d);
Matrix& operator=(const Matrix&);
friend Matrix operator*(const Matrix& lhs, const Matrix& rhs)
{
Matrix ret(0,0,0,0);
ret.matr[0][0] = lhs.matr[0][0]*rhs.matr[0][0] + lhs.matr[0]
[1]*rhs.matr[1][0];
ret.matr[0][1] = lhs.matr[0][0]*rhs.matr[0][1] + lhs.matr[0]
[1]*rhs.matr[1][1];
ret.matr[1][0] = lhs.matr[1][0]*rhs.matr[0][0] + lhs.matr[1]
[1]*rhs.matr[1][0];
ret.matr[1][1] = lhs.matr[1][0]*rhs.matr[0][1] + lhs.matr[1]
[1]*rhs.matr[1][1];
return ret;
}
};
#
Matrix::Matrix(long a, long b, long c, long d)
{
this->matr[0][0] = a;
资源评论
xuzhe1233212012-10-26仅供参考学习
流觞的风2013-01-04只有代码，没有时间复杂度的分析过程
liuwencaia2014-02-03用数学公式求解- just_yun2012-09-27非常有用，提供了fibonacci series的求解时间复杂度最小方法 c＋＋也没有语法错误 好！！
- handonglixin2013-10-16可供参考用
cuirongcun
- 粉丝: 4
- 资源: 5
