斐波那契数列(递归+迭代)

简介: 斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(Leonardo Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、3

什么是斐波那契数列


斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(Leonardo Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、3


通俗地来讲,斐波那契数列就是从第三位数字开始,每位的值是其前两位的和


递归写法


使用递归方法写十分简单

从第三位数字开始,每位的值是其前两位的和


f(0) = 1

f(1) = 1

f(n) = f(n-1)+f(n-2)(n>3)

代码如下:


long long feibonahi(int n)
{
  if (n <= 2)
  {
  return 1;
  }
  else
  {
  return feibonahi(n - 1) + feibonahi(n - 2);
  }
}


使用递归写法的缺点

我们分析一下递归算法的时间复杂度





20c1e7ed414f40ae8a4c212757adaac5.png



可以看出这个递归方法的时间复杂度是O(2^n)


可能这是没觉得时间复杂度是O(2^n)是多大的事,所以接下来我们计算一下传不同参数,这个递归算法的运行时间:


#include <stdio.h>
#include <time.h>
long long Fib(int n)
{
  if (n <= 2)
  {
  return 1;
  }
  else
  {
  return Fib(n - 1) + Fib(n - 2);
  }
}
int main()
{
  int begin1 = clock();
  Fib(10);
  int end1 = clock();
  int begin2 = clock();
  Fib(20);
  int end2 = clock();
  int begin3 = clock();
  Fib(30);
  int end3 = clock();
  int begin4 = clock();
  Fib(40);
  int end4 = clock();
  int begin5 = clock();
  Fib(50);
  int end5 = clock();
  printf("end1:%d\n", end1 - begin1);
  printf("end2:%d\n", end2 - begin2);
  printf("end3:%d\n", end2 - begin3);
  printf("end4:%d\n", end4 - begin4);
  printf("end5:%d\n", end5 - begin5);
  return 0;
}



下面我们可以看到:

从参数从10~40的运行时间还算快,然而将50传入函数中,可以看到,会运行一段时间




62fcea9752824b5991e29d8051f3a696.png


所以使用递归方法求斐波那契数列在理论上可行,但是在实际中是不可取的一个方法


另外,我们在这也看一下2^N的“威力”


N==10,2^N = 1024

N==20,2^N = 100万

N==30,2^N = 10亿

N==40,2^N = 1万亿

N==50,2^N = 很大很大的数

所以我们不能使用递归算法,接下来我们写一个迭代方法


迭代写法(效率高)

int feibonahi2(int n)
{
  if (n == 1 || n == 2)
  {
  return 1;
  }
  int a = 1;
  int b = 1;
  int c = 1;
  while (n > 2)
  {
  c = a + b;
  a = b;
  b = c;
  n--;
  }
  return c;
}



这个算法的时间复杂度是O(N),上面的递归写法要好的太多太多


目录
相关文章
|
Linux 数据处理 C++
Linux系统编程 C/C++ 以及Qt 中的零拷贝技术: 从底层原理到高级应用(一)
Linux系统编程 C/C++ 以及Qt 中的零拷贝技术: 从底层原理到高级应用
582 0
|
Ubuntu Linux 网络安全
使用Kali Linux虚拟机破解WiFi密码的一波三折及详细操作步骤
使用Kali Linux虚拟机破解WiFi密码的一波三折及详细操作步骤
3497 0
使用Kali Linux虚拟机破解WiFi密码的一波三折及详细操作步骤
|
网络协议 Java
【工具】Mermaid + 大模型画流程图
最近看面试文章关于TCP三次握手和四次挥手的文章,时常会看到有类似的图去描述这样的过程。当然觉得这样的图还是蛮规范的,属于流程图的一种,是否有工具可以自动生成呢?但没有细想,昨天刷V2EX看到也有老哥发出了这样的问题。于是顺着评论区大佬的回答,我GET到了一个工具Mermaid 这里三次握手的图取自小林coding的文章
1369 0
|
6月前
|
人工智能 自然语言处理 测试技术
自然语言生成代码一键搞定!Codex CLI:OpenAI开源终端AI编程助手,代码重构+测试全自动
Codex CLI是OpenAI推出的轻量级AI编程智能体,基于自然语言指令帮助开发者高效生成代码、执行文件操作和进行版本控制,支持代码生成、重构、测试及数据库迁移等功能。
950 0
自然语言生成代码一键搞定!Codex CLI:OpenAI开源终端AI编程助手,代码重构+测试全自动
|
芯片
利用两个IO口检测6个按键
【8月更文挑战第23天】在资源受限的情况下,可通过巧妙设计使用两个I/O口检测六个按键。硬件连接上,六个按键以不同组合方式连接至IO1和IO2:键1连IO1与地;键2连IO2与地;键3同时连IO1和IO2;键4经电阻接IO1并接地;键5同样处理但接IO2;键6则各自经电阻连接至IO1和IO2后接地。软件方面,设置两I/O为输入模式并启用上拉电阻,依据高低电平的不同组合判断具体按键。此法需注意实际应用中的参数选择与优化。
411 2
|
C++
QT第一个程序命名空间详解,解释ui_widget的和xxx.cpp的联系
QT第一个程序命名空间详解,解释ui_widget的和xxx.cpp的联系
401 0
|
机器学习/深度学习 人工智能 Cloud Native
福利「Flink Forward Asia 2023 」视频合集!
2023 年 12 月 9 日,Flink Forward Asia 2023 在北京圆满结束。本届大会共有 70+ 演讲议题、30+ 一线大厂技术与实践分享。现所有专场回放视频已经出炉,并在开发者社区上线。
6282 2
福利「Flink Forward Asia 2023 」视频合集!
|
Kubernetes 安全 数据安全/隐私保护
ACK场景下应用程序安全访问云资源最佳实践
在实际的容器安全实践中,怎么样避免应用程序永久访问密钥。本文会介绍基于云原生的产品能力来实现无AK方案。
549 6
ACK场景下应用程序安全访问云资源最佳实践
|
算法 安全 Java
[转载]加密解密算法【RSA、AES、DES、MD5】介绍和使用
为了防止我们的数据泄露,我们往往会对数据进行加密,特别是敏感数据,我们要求的安全性更高。下面将介绍几种常用的加密算法使用。这些算法的加密对象都是基于二进制数据,如果要加密字符串就使用统一编码(如:utf8)进行编码后加密。
2906 0