热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

O(logn)求Fibonacci数列[算法]

From:http:zhedahht.blog.163.comblogstatic25411174200722991933440题目:定义Fibonacci数


From:  http://zhedahht.blog.163.com/blog/static/25411174200722991933440/


 题目:定义Fibonacci数列如下:

        /  0                      n=0
f(n)=      1                      n=1
        \  f(n-1)+f(n-2)          n=2

输入n,用最快的方法求该数列的第n项。

分析:在很多C语言教科书中讲到递归函数的时候,都会用Fibonacci作为例子。因此很多程序员对这道题的递归解法非常熟悉,看到题目就能写出如下的递归求解的代码。

///////////////////////////////////////////////////////////////////////
// Calculate the nth item of Fibonacci Series recursively
///////////////////////////////////////////////////////////////////////
long long Fibonacci_Solution1(unsigned int n)
{
      int result[2] = {0, 1};
      if(n <2)
            return result[n];

      return Fibonacci_Solution1(n - 1) + Fibonacci_Solution1(n - 2);
}

但是,教科书上反复用这个题目来讲解递归函数,并不能说明递归解法最适合这道题目。我们以求解f(10)作为例子来分析递归求解的过程。要求得f(10),需要求得f(9)和f(8)。同样,要求得f(9),要先求得f(8)和f(7)……我们用树形结构来表示这种依赖关系

                  f(10)
               /        \
            f(9)         f(8)
          /     \       /    \
       f(8)     f(7)  f(7)   f(6)
      /   \     /   \
 
   f(7)  f(6)  f(6) f(5)

我们不难发现在这棵树中有很多结点会重复的,而且重复的结点数会随着n的增大而急剧增加。这意味这计算量会随着n的增大而急剧增大。事实上,用递归方法计算的时间复杂度是以n的指数的方式递增的。大家可以求Fibonacci的第100项试试,感受一下这样递归会慢到什么程度。在我的机器上,连续运行了一个多小时也没有出来结果。

其实改进的方法并不复杂。上述方法之所以慢是因为重复的计算太多,只要避免重复计算就行了。比如我们可以把已经得到的数列中间项保存起来,如果下次需要计算的时候我们先查找一下,如果前面已经计算过了就不用再次计算了。

更简单的办法是从下往上计算,首先根据f(0)和f(1)算出f(2),在根据f(1)和f(2)算出f(3)……依此类推就可以算出第n项了。很容易理解,这种思路的时间复杂度是O(n)。

///////////////////////////////////////////////////////////////////////
// Calculate the nth item of Fibonacci Series iteratively
///////////////////////////////////////////////////////////////////////
long long Fibonacci_Solution2(unsigned n)
{
      int result[2] = {0, 1};
      if(n <2)
            return result[n];

      long long  fibNMinusOne= 1;
      long long  fibNMinusTwo = 0;
      long long  fibN = 0;
      for(unsigned int i = 2; i <= n; ++ i)
      {
            fibN = fibNMinusOne + fibNMinusTwo;

            fibNMinusTwo = fibNMinusOne;
            fibNMinusOne= fibN;
      }

       return fibN;
}

这还不是最快的方法。下面介绍一种时间复杂度是O(logn)的方法。在介绍这种方法之前,先介绍一个数学公式:

{f(n), f(n-1), f(n-1), f(n-2)} ={1, 1, 1,0}n-1

(注:{f(n+1), f(n), f(n), f(n-1)}表示一个矩阵。在矩阵中第一行第一列是f(n+1),第一行第二列是f(n),第二行第一列是f(n),第二行第二列是f(n-1)。)

有了这个公式,要求得f(n),我们只需要求得矩阵{1, 1, 1,0}的n-1次方,因为矩阵{1, 1, 1,0}的n-1次方的结果的第一行第一列就是f(n)。这个数学公式用数学归纳法不难证明。感兴趣的朋友不妨自己证明一下。

现在的问题转换为求矩阵{1, 1, 1, 0}的乘方。如果简单第从0开始循环,n次方将需要n次运算,并不比前面的方法要快。但我们可以考虑乘方的如下性质:

        /  an/2*an/2                      n为偶数时
an=
        \  a(n-1)/2*a(n-1)/2            n为奇数时

要求得n次方,我们先求得n/2次方,再把n/2的结果平方一下。如果把求n次方的问题看成一个大问题,把求n/2看成一个较小的问题。这种把大问题分解成一个或多个小问题的思路我们称之为分治法。这样求n次方就只需要logn次运算了。

实现这种方式时,首先需要定义一个2×2的矩阵,并且定义好矩阵的乘法以及乘方运算。当这些运算定义好了之后,剩下的事情就变得非常简单。完整的实现代码如下所示。

#include

///////////////////////////////////////////////////////////////////////
// A 2 by 2 matrix
///////////////////////////////////////////////////////////////////////
struct Matrix2By2
{
      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) 
      {
      }

      long long m_00;
      long long m_01;
      long long m_10;
      long long m_11;
};

///////////////////////////////////////////////////////////////////////
// Multiply two matrices
// Input: matrix1 - the first matrix
//        matrix2 - the second matrix
//Output: the production of two matrices
///////////////////////////////////////////////////////////////////////
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);
}

///////////////////////////////////////////////////////////////////////
// The nth power of matrix
// 1  1
// 1  0
///////////////////////////////////////////////////////////////////////
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;
}

///////////////////////////////////////////////////////////////////////
// Calculate the nth item of Fibonacci Series using devide and conquer
///////////////////////////////////////////////////////////////////////
long long Fibonacci_Solution3(unsigned int n)
{
      int result[2] = {0, 1};
      if(n <2)
            return result[n];

      Matrix2By2 PowerNMinus2 = MatrixPower(n - 1);
      return PowerNMinus2.m_00;
}



推荐阅读
  • 本文讨论了clone的fork与pthread_create创建线程的不同之处。进程是一个指令执行流及其执行环境,其执行环境是一个系统资源的集合。在调用系统调用fork创建一个进程时,子进程只是完全复制父进程的资源,这样得到的子进程独立于父进程,具有良好的并发性。但是二者之间的通讯需要通过专门的通讯机制,另外通过fork创建子进程系统开销很大。因此,在某些情况下,使用clone或pthread_create创建线程可能更加高效。 ... [详细]
  • 本文介绍了最长上升子序列问题的一个变种解法,通过记录拐点的位置,将问题拆分为左右两个LIS问题。详细讲解了算法的实现过程,并给出了相应的代码。 ... [详细]
  • 提升Python编程效率的十点建议
    本文介绍了提升Python编程效率的十点建议,包括不使用分号、选择合适的代码编辑器、遵循Python代码规范等。这些建议可以帮助开发者节省时间,提高编程效率。同时,还提供了相关参考链接供读者深入学习。 ... [详细]
  • 本文由编程笔记#小编为大家整理,主要介绍了logistic回归(线性和非线性)相关的知识,包括线性logistic回归的代码和数据集的分布情况。希望对你有一定的参考价值。 ... [详细]
  • 生成式对抗网络模型综述摘要生成式对抗网络模型(GAN)是基于深度学习的一种强大的生成模型,可以应用于计算机视觉、自然语言处理、半监督学习等重要领域。生成式对抗网络 ... [详细]
  • 本文介绍了设计师伊振华受邀参与沈阳市智慧城市运行管理中心项目的整体设计,并以数字赋能和创新驱动高质量发展的理念,建设了集成、智慧、高效的一体化城市综合管理平台,促进了城市的数字化转型。该中心被称为当代城市的智能心脏,为沈阳市的智慧城市建设做出了重要贡献。 ... [详细]
  • CSS3选择器的使用方法详解,提高Web开发效率和精准度
    本文详细介绍了CSS3新增的选择器方法,包括属性选择器的使用。通过CSS3选择器,可以提高Web开发的效率和精准度,使得查找元素更加方便和快捷。同时,本文还对属性选择器的各种用法进行了详细解释,并给出了相应的代码示例。通过学习本文,读者可以更好地掌握CSS3选择器的使用方法,提升自己的Web开发能力。 ... [详细]
  • 本文介绍了九度OnlineJudge中的1002题目“Grading”的解决方法。该题目要求设计一个公平的评分过程,将每个考题分配给3个独立的专家,如果他们的评分不一致,则需要请一位裁判做出最终决定。文章详细描述了评分规则,并给出了解决该问题的程序。 ... [详细]
  • 本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度,要求从最低点跳跃到最高点,每次跳跃的距离不超过D,并且不能改变给定的顺序。通过建立差分约束系统,将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法,并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]
  • sklearn数据集库中的常用数据集类型介绍
    本文介绍了sklearn数据集库中常用的数据集类型,包括玩具数据集和样本生成器。其中详细介绍了波士顿房价数据集,包含了波士顿506处房屋的13种不同特征以及房屋价格,适用于回归任务。 ... [详细]
  • 不同优化算法的比较分析及实验验证
    本文介绍了神经网络优化中常用的优化方法,包括学习率调整和梯度估计修正,并通过实验验证了不同优化算法的效果。实验结果表明,Adam算法在综合考虑学习率调整和梯度估计修正方面表现较好。该研究对于优化神经网络的训练过程具有指导意义。 ... [详细]
  • CF:3D City Model(小思维)问题解析和代码实现
    本文通过解析CF:3D City Model问题,介绍了问题的背景和要求,并给出了相应的代码实现。该问题涉及到在一个矩形的网格上建造城市的情景,每个网格单元可以作为建筑的基础,建筑由多个立方体叠加而成。文章详细讲解了问题的解决思路,并给出了相应的代码实现供读者参考。 ... [详细]
  • Java学习笔记之面向对象编程(OOP)
    本文介绍了Java学习笔记中的面向对象编程(OOP)内容,包括OOP的三大特性(封装、继承、多态)和五大原则(单一职责原则、开放封闭原则、里式替换原则、依赖倒置原则)。通过学习OOP,可以提高代码复用性、拓展性和安全性。 ... [详细]
  • 3.223.28周学习总结中的贪心作业收获及困惑
    本文是对3.223.28周学习总结中的贪心作业进行总结,作者在解题过程中参考了他人的代码,但前提是要先理解题目并有解题思路。作者分享了自己在贪心作业中的收获,同时提到了一道让他困惑的题目,即input details部分引发的疑惑。 ... [详细]
  • JDK源码学习之HashTable(附带面试题)的学习笔记
    本文介绍了JDK源码学习之HashTable(附带面试题)的学习笔记,包括HashTable的定义、数据类型、与HashMap的关系和区别。文章提供了干货,并附带了其他相关主题的学习笔记。 ... [详细]
author-avatar
自行脑补
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有