本文共 2239 字，大约阅读时间需要 7 分钟。

剑指offer——面试题9：求斐波那切数列的四种方法

另一个相关的链接：

Solution1:递归法

代码复杂度为$O(2^n)$，简单却不是一个好思路呀~

class Solution {public:    int Fibonacci(int n) {        if(n==1 || n==2) return 1;        return Fibonacci(n-1)+Fibonacci(n-2);    }};

Solution2:迭代法

时间复杂度$O(n)$参考清华大学邓俊辉老师的数据结构中的算法写成。真的是其妙极了~

class Solution {public:    int Fibonacci(int n) {        int f=0,g=1;//fib(0)=0,fib(1)=1        if(n==0)            return f;        else if(n==1 || n==2)            return g;        while(1

复杂度为$O(n)$!!!

Solution3:矩阵法

时间复杂度$O(logn)$

//定义2×2矩阵；  struct Matrix2by2  {      //数据成员      int m00;      int m01;      int m10;      int m11;      //构造函数      Matrix2by2(int m_00,int m_01,int m_10,int  m_11)      {          m00 = m_00;          m01 = m_01;          m10 = m_10;          m11 = m_11;      }  };  //定义2×2矩阵的乘法运算  Matrix2by2 MatrixMultiply(const Matrix2by2& matrix1,const Matrix2by2& matrix2)  {      Matrix2by2 matrix12(1,1,1,0);      matrix12.m00 = matrix1.m00 * matrix2.m00 + matrix1.m01 * matrix2.m10;      matrix12.m01 = matrix1.m00 * matrix2.m01 + matrix1.m01 * matrix2.m11;      matrix12.m10 = matrix1.m10 * matrix2.m00 + matrix1.m11 * matrix2.m10;      matrix12.m11 = matrix1.m10 * matrix2.m01 + matrix1.m11 * matrix2.m11;      return matrix12;  }  //定义2×2矩阵的幂运算  Matrix2by2 MatrixPower(unsigned int n)  {      Matrix2by2 matrix(1,1,1,0);      if (n == 1)      {          matrix = Matrix2by2(1,1,1,0);      }      else if (n % 2 == 0)      {          matrix = MatrixPower(n / 2);          matrix = MatrixMultiply(matrix, matrix);      }      else if (n % 2 == 1)      {          matrix = MatrixPower((n-1) / 2);          matrix = MatrixMultiply(matrix, matrix);          matrix = MatrixMultiply(matrix, Matrix2by2(1,1,1,0));      }      return matrix;  }  //计算Fibnacci的第n项  int fib(unsigned int n)  {      if (n == 0)          return 0;      if (n == 1)          return 1;      Matrix2by2 fibMatrix = MatrixPower(n-1);      return fibMatrix.m00;  }

Solution4:公式法

时间复杂度$O(1)$

class Solution {public:    int Fib(int n) {        const double s = sqrt(5);        return (pow((1+s)/2, n) - pow((1-s)/2, n))/s;    }}