首页 > 其他分享 >时间复杂度(斐波那契)和空间复杂度

时间复杂度(斐波那契)和空间复杂度

时间:2024-01-09 21:35:52浏览次数:24  
标签:复杂度 long 斐波 空间 那契 size

1.0时间复杂度(斐波那契)

//计算阶层递归Fac的时间复杂度
long long Fac(size_t N)
{
  if(0==N)
    return 1;
  return Fac(N-1)*N;
}

该算法的时间复杂度度很稳定:O(N)

//计算斐波那契数列递归Fib的时间复杂度
long long Fib(size_t N)
{
  if(N<3)
    return 1;
  return Fib(N-1)+Fib(N-2);
}

F(N)=O(2^N);

斐波那契数列的递归写法完全是一个实际上没用的算法,因为运行速度很慢

2.0空间复杂度

定义:

  • 空间复杂度也是一个数学函数表达式,是对一个算法在运行过程中临时占用存储空间大小的量度。
  • 空间复杂度不是程序占用了多少字节的空间,因为这个也没太大的意义,所以空间复杂度算的是变量的个数,也用大O渐进表示法
  • 注:函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了,因此空间复杂度主要通过函数在运行时候显示申请的额外空间(比如 递归)来确定
//计算BubbleSort的空间复杂度?
void BubbleSort(int* a,int n)
{
  assert(a);
  for(size_t end=n;end>0;--end)
  {
    int exchange=0;
    for(size_t=1;i<end;++i)
    {
      if(a[i-1]>a[i])
      {
        Swap(&a[i-1],&a[i]);
        exchange=1;
      }
    }
    if(exchange==0)
      break;
  }
}

空间复杂度:O(1)
































































标签:复杂度,long,斐波,空间,那契,size
From: https://blog.51cto.com/u_16351083/9165542

相关文章

  • 时间复杂度(常数循环、strchr、冒泡排序、二分查找)
    1.1常数循环//计算复杂度voidFunc4(intk){intcount=0;for(intk=0;k<100;++k){++count;}printf("%d\n",count);}时间复杂度为:O(1)  注:O(1)不是代表算法只能运行一次,是常数次1.2strchr的时间复杂度//计算strchar的时间复杂度constchar*strchr(constc......
  • 算法的时间复杂度和空间复杂度
    1.算法效率1.1如何衡量一个算法的好坏longlongFib(intN){if(N<3){return1;}returnFib(N-1)+Fib(N-2);}斐波那契数列的递归实现方式非常简洁,但是简洁一定好吗?那应该如何衡量其好与坏呢?1.2算法的复杂度衡量一个算法的好坏,一般是从时间和空间上来衡量的,即时间......
  • 【C++】STL 容器 - list 双向链表容器 ① ( 容器特点 | 容器操作时间复杂度 | 构造函
    文章目录一、list双向链表容器简介1、容器特点2、容器操作时间复杂度3、遍历访问5、头文件二、list双向链表容器构造函数1、默认无参构造函数2、创建包含n个相同元素的list双向链表3、使用初始化列表构造list双向链表4、使用另外一个list容器构造list双向链表容器......
  • Python时间复杂度计算题答案
    评论题目链接答案时间复杂度:O(n)。分析:这段代码遍历了n次,所以时间复杂度是线性的,即O(n)。时间复杂度:O(n^2)。分析:两个嵌套的循环,每个循环都运行n次,因此时间复杂度是二次的,即O(n^2)。时间复杂度:O(logn)。分析:每次循环i都翻倍,因此循环的次数是log2(n)。时间复杂度:O(n*m)。分析:......
  • Vue检测密码复杂度方法
    Vue检测密码复杂度方法<!--检测密码复杂度方法--><template><div><inputtype="password"v-model="password"@input="checkPasswordComplexity"><divv-if="complexityMessage">{{complexityMessa......
  • Halo2简单使用-斐波那契数列
    电路设计Halo2是基于PLONK算法的零知识证明框架,使用Rust语言。在Halo2中要证明你掌握斐波那契数列,例如Fib(10)=55。则需要将你的每一步计算过程(秘密的)罗列出来。并由程序(电路)来进行验证,生成证明。在PLONK算法里,我们使用表格来进行计算跟踪,例如:abc112123235358581381321132134......
  • 番外---时间复杂度表
    备注:Y为可以,N为不可以问题规模n可用算法的时间复杂度O(log2n)         O(n)            O(nlog2n)         O(n^2)O(2^n)  O(n!)n<=11YYYYYYn<=25YYYYYNn<=5000......
  • Halo2简单应用-斐波那契示例
    电路设计Halo2是基于PLONK算法的零知识证明框架,使用Rust语言。在Halo2中要证明你掌握斐波那契数列,例如Fib(10)=55。则需要将你的每一步计算过程(秘密的)罗列出来。并由程序(电路)来进行验证,生成证明。在PLONK算法里,我们使用表格来进行计算跟踪,例如:abr112123......
  • Java-与斐波那契数列相关的变体问题
    变体问题指的是提问的方式不一样了,但是解决问题的方法还是用斐波那契数列来解。——写在前面的话。一、变体1-兔子问题1.问题描述第一个月,有一对未成熟的兔子第二个月上述的一对兔子成熟第三个月,他们能产下一对小兔子所有兔子遵循相同规律,求第n个月的兔子个数2.分析例子假设我要求......
  • 空间复杂度
    空间复杂度概念:和时间复杂度一样,时对一个算法在运行过程中临时占用存储空间大小的量度。空间复杂度不是程序占用了多少bytes的空间,因为这也没什么意义,所以空间复杂度算的是变量的个数,也使用大O监禁表示法。voidBubbleSort(int*a,inn){assert(a)for(size_tend=n;end>0;......