斐波那契数列

作者:金牛区福生殡葬服务部 来源:www.cdfsbz.com 发布时间:2017-09-07 13:14:16
斐波那契数列 斐波那契数列 递归实现 /** * @author 韦轩 * @time 2015/07/26 * @brief 递归求菲波那切数列的第N项 * @param n,无符号的整数,要求的第N项 * @return 返回第N项 * */ long long getNthNumberWithRecursion(unsigned int n) { int result[2] = { 0, 1 }; if (n < 2) return result[n]; return getNthNumberWithRecursion(n - 1) + getNthNumberWithRecursion(n - 2); } 时间复杂度:
T(n) = T(n - 1) + T(n - 2) + O(1),很容易得到T(n) = O(1.618 ^ n)(黄金分割点,(1+5√)/2 ) 空间复杂度取决于递归的深度是O(N) 迭代实现 /** * @author 韦轩 * @time 2015/07/26 * @brief 迭代求菲波那切数列的第N项 * @param n,无符号的整数,要求的第N项 * @return 返回第N项 * */ long long getNthNumberWithNoRecursion(unsigned int n) { int result[2] = { 0, 1 }; if (n < 2) return result[n]; long long total = 0, first = 0, second = 1; for (unsigned int i = 2; i <= n; i++) { total = first + second; first = second; second = total; } return total; }

-时间复杂度:O(N)
-空间复杂度:O(1)

矩阵实现

我们把Fibonacci数列中相邻的两项:F(n)和F(n - 1)写成一个2x1的矩阵,然后对其进行变形
[FnF(n−1)]=[F(n−1)+F(n−2)F(n−1)]=[1×F(n−1)+1×F(n−2)1×F(n−1)+0×F(n−2)]=[1110]×[F(n−1)F(n−2)]
上面的式子可以继续化简
[FnF(n−1)]=[1110]n−1×[F1F0]=[1110]n−1×[10]
呃呃。。。
只要对这个二阶方阵求n - 1次方,最后取结果方阵第一行第一列的数字就是Fn的值。
注意:幂运算是可以二分加速的。
an=??? an/2×an/2,an/2×an/2×a,n 偶数 n 是奇数
所以,时间复杂度是logN

/** * @author 韦轩 * @time 2015/07/26 * @brief 二维矩阵 * */ struct Matrix2By2 { long long m_00; long long m_01; long long m_10; long long m_11; Matrix2By2 ( long long m00 = 0, long long m01 = 0, long long m10 = 0, long long m11 = 0 ) :m_00(m00), m_01(m01), m_10(m10), m_11(m11){} }; /** * @author 韦轩 * @time 2015/07/26 * @brief 矩阵相乘 * @param 两个矩阵 * @return 矩阵相乘的结果矩阵 * */ Matrix2By2 MatrixMultiply(const Matrix2By2& matrix1,const Matrix2By2& matrix2) { return Matrix2By2( matrix1.m_00 * matrix2.m_00 + matrix1.m_01 * matrix2.m_10, matrix1.m_00 * matrix2.m_01 + matrix1.m_01 * matrix2.m_11, matrix1.m_10 * matrix2.m_00 + matrix1.m_11 * matrix2.m_10, matrix1.m_10 * matrix2.m_01 + matrix1.m_11 * matrix2.m_11); } /** * @author 韦轩 * @time 2015/07/26 * @brief 矩阵的N次方 * @param * @return */ Matrix2By2 MatrixPower(unsigned int n) { assert(n > 0); Matrix2By2 matrix; 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; } /** * @author 韦轩 * @time 2015/07/26 * @brief 使用矩阵计算获得菲波那切数列的第N项 * @param * @return * */ long long getNthNumberWithMatrix(unsigned int n) { int result[2] = { 0, 1 }; if (n < 2) return result[n]; Matrix2By2 PowerNMinus2 = MatrixPower(n - 1); return PowerNMinus2.m_00; } 时间复杂度:O(logN) 空间复杂度:O(1)

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:仙桃网站建设 http://xiantao.45qun.com

  • 上一篇:机器学习day17 机器学习实战FP-growth挖掘频繁项集
  • 下一篇:最后一页
  • 
    COPYRIGHT © 2015 金牛区福生殡葬服务部 ALL RIGHTS RESERVED.
    购买cdfsbz.com友情链接、项目合作请联系客服QQ:2500-38-100 邮箱:2500-38-100#QQ.com(#换@)
    本站所有原创信息,未经许可请勿任意转载或复制使用 网站地图 技术支持:肥猫科技
    精彩专题:网站建设
    购买本站友情链接、项目合作请联系客服QQ:2500-38-100