精华内容
下载资源
问答
  • 斐波那契数 时间,空间复杂度大O的渐进表示法推导大O阶方法:时间复杂度时间复杂度的概念空间复杂度空间复杂度的概念 大O的渐进表示法 推导大O阶方法: 1、用常数1取代运行时间中的所有加法常数。 2、在修改后的...

    大O的渐进表示法

    推导大O阶方法:

    1、用常数1取代运行时间中的所有加法常数。
    2、在修改后的运行次数函数中,只保留最高阶项。
    3、如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。

    注意:有些算法的时间复杂度存在最好、平均和最坏情况:
    最坏情况:任意输入规模的最大运行次数(上界)
    平均情况:任意输入规模的期望运行次数
    最好情况:任意输入规模的最小运行次数(下界)

    例如:在一个长度为N数组中搜索一个数据x
    最好情况:1次找到
    最坏情况:N次找到
    平均情况:N/2次找到

    在实际中一般情况关注的是算法的最坏运行情况,所以数组中搜索数据时间复杂度为O(N)

    时间复杂度

    时间复杂度的概念

    时间复杂度的定义:在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。一个算法执行所耗费的时间,从理论上说,是不能算出来的,只有你把你的程序放在机器上跑起来,才能知道。但是我们需要每个算法都上机测试吗?是可以都上机测试,但是这很麻烦,所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复杂度。

    递归算法的时间复杂度:递归的总次数*每次递归的数量。

    斐波那契数列,又称黄金分割数列,指的是这样一个数列:0、1、1、2、3、5、8、13、21、34、……

    递归求斐波那契数时间复杂度为O(2^N)

    时间复杂度分析:
      求解F(n),必须先计算F(n-1)和F(n-2),计算F(n-1)和F(n-2),又必须先计算F(n-3)和F(n-4)…以此类推,直至必须先计算F(1)和F(0),然后逆推得到F(n-1)和F(n-2)的结果,从而得到F(n)要计算很多重复的值,在时间上造成了很大的浪费,算法的时间复杂度随着N的增大呈现指数增长,时间的复杂度为O(2^n),即2的n次方

    long long Fib(size_t N)
    {
    	return N < 2 ? N : Fib(N - 1) + Fib(N - 2);
    }
    

    这种方法看似代码简单,实际操作起来非常繁琐,有兴趣的朋友可是试试给个100运行一下,不过可能得等上几个小时才会出结果哦

    递归求斐波那契数时间复杂度为O(N)

    尾递归法
    如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时,这个递归调用就是尾递归。

    long long Fib(long  long first, long  long second, long long n)
    {
    	if (n < 3)
    		return 1;
    	if (3 == n)
    	{
    		return first + second;
    	}
    	return Fib(second, first + second, n - 1);
    }
    

    用循环方法来实现时间复杂度为O(N)的斐波那契数

    long long Fib(int n)
    {
    	long long ret = 0;
    	long long first = 1, second = 1;
    	for (int i = 3; i <= n; i++)
    	{
    		ret = first + second;
    		first = second;
    		second = ret;
    	}
    	return ret;
    }
    

    空间复杂度

    空间复杂度的概念

    空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。=空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似,也使用大O渐进表示法。

    递归算法的空间复杂度:递归的深度*每次递归创建变量的个数。

    空间复杂度为O(N)的斐波那契数

    long long Fib(int n)
    {
    	long long*p = (long long*)malloc(sizeof(long long)*n);
    	assert(p != NULL);
    	p[0] = 1, p[1] = 1;
    	for (int i = 2; i < n; i++)
    	{
    		p[i] = p[i - 1] + p[i - 2];
    	}
    	long long ret = p[n - 1];  //定义一个临时变量去接收p[n-1],以便于最后释放这个内存空间
    	free(p);
    	return ret;
    
    展开全文
  • 提起斐波那契数列,首先想到的大概都是递归,但是其时间复杂度并非最优,其时间复杂度为O(2^N)。具体分析可以参考:Fibonacci 方法二 循环 递归之所以效率低下,是因为需要重复的计算一些中间变量。而利用循环可以...

    方法一 递归

    提起斐波那契数列,首先想到的大概都是递归,但是其时间复杂度并非最优,其时间复杂度为O(2^N)。具体分析可以参考:Fibonacci

    方法二 循环

    递归之所以效率低下,是因为需要重复的计算一些中间变量。而利用循环可以通过存储中间变量来减小计算量,其时间复杂度为O(N)。


    方法三 矩阵乘法

    利用矩阵乘法加上分治的思想,可以将其时间复杂度降低到O(log2^n).具体的代码如下。关于其思路分析可以参考:Fibonacci

    #include<stdio.h>
    
    typedef struct MTX{
    	int m00;
    	int m01;
    	int m10;
    	int m11;
    }mtx;
    mtx mtx0;
    
    mtx m_multiply(mtx a, mtx b)
    {
    	mtx c;
    	c.m00=a.m00*b.m00+a.m01*b.m10;
    	c.m01=a.m00*b.m01+a.m01*b.m11;
    	c.m10=a.m10*b.m00+a.m11*b.m10;
    	c.m11=a.m10*b.m01+a.m11*b.m11;
    	return c;
    }
    
    mtx m_power(int k)
    {
    	mtx m;
    	
    	if(1==k)
    	{
    		m=mtx0;
    		return m;
    	}
    	else if(0==k%2)
    	{
    		m=m_multiply(m_power(k/2),m_power(k/2));
    		return m;
    	}
    	else
    	{
    		m=m_multiply(m_power((k-1)/2),m_power((k-1)/2));
    		m=m_multiply(m,mtx0);
    		return m;
    	}
    }
    int fibonacci(int n)
    {
    	int m;
    	mtx mtx1;
    	
    	int t[2]={0, 1};
    	if(n<3)
    		return t[n];
    	else
    		mtx1=m_power(n-2);
    	return mtx1.m00;
    }
    
    int main(void)
    {
    	mtx0.m00=1;
    	mtx0.m01=1;
    	mtx0.m10=1;
    	mtx0.m11=0;
    	int n=8;
    	
    	int m=fibonacci(n);
    	printf("Fibonacci(%d)=%d",n,m);
    	return m;
    }


    展开全文
  • 试分别分析两种算法的时间复杂度。   递归方式 递归方式代码: 递归结束条件可以不同,如果数列从第一个开始且为1,那么就是如下结束条件。 如果从第0个开始且第0个为0,那么结束条件就会改变:n等于0时返回0...

    问题

    来自王道考研数据结构书籍,思维拓展

    斐波那契数列有两种常用的算法:递归算法和非递归算法。试分别分析两种算法的时间复杂度。

     

    递归方式

    递归方式代码:
    递归结束条件可以不同,如果数列从第一个开始且为1,那么就是如下结束条件。
    如果从第0个开始且第0个为0,那么结束条件就会改变:n等于0时返回0,n等于1时返回1

    #include <stdio.h>
    #include <stdlib.h>
    
    int Fibonacci(int n){
    	if(n==1||n==2)
    		return 1;
    	else
    		return Fibonacci(n-1)+Fibonacci(n-2);
    } 
    
    int main(int argc, char *argv[]) {
    	int n;
    	scanf("%d",&n);
    	int result = Fibonacci(n);
    	printf("%d",result);
    	return 0;
    }
    

    时间复杂度可通过下图分析:
    在这里插入图片描述
    如果是一个满二叉树的话,其时间复杂度就是O(2^n)。但实际上并不是满二叉树,所以比这个要小一点。网上有确切的值以及推导过程,大家可以看看。

     

    非递归方式

    代码如下:

    #include<stdio.h>
    #include<stdlib.h>
    
    int Fibonacci(int n){
    	if(n<=2){
    		return 1;
    	}else{
    		int num1=1;
    		int num2=1;
    		int i;
    		for(i=2;i<n;i++){
    			num2=num1+num2;
    			num1=num2-num1;
    		}
    		return num2;
    	}
    }
    
    int main(){
    	int n;
    	scanf("%d",&n);
    	int result=Fibonacci(n);
    	printf("%d",result);
    }
    

    直接看for循环即可,语句重复执行的次数是n的数量级,所以时间复杂度为O(n)。

    展开全文
  • 斐波那契数列 递归算法 循环算法 优化递归算法 以及它们的时间复杂度,空间复杂度分析

    斐波那契数列

    【含义】:

    斐波那契数列,又称黄金分割数列,指的是这样一个数列:0、1、1、2、3、5、8、13、21、34、……在数学上,斐波纳契数列以如下被以递归的方法定义:F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2,n∈N*)在现代物理、准晶体结构、化学等领域,斐波纳契数列都有直接的应用,为此,美国数学会从1963起出版了以《斐波纳契数列季刊》为名的一份数学杂志,用于专门刊载这方面的研究成果。


    用C求取第n个斐波那契数


    【时间复杂度】:递归总次数*每次递归的次数

    【空间复杂度】:递归的深度*每次递归空间的大小

    【递归深度】:树的高度(递归的过程是一个”二叉树”)

    【一般算法O(n)计算方法】:
    - 用常数1取代运行时间中的所有加法常数
    - 在修改后的运行次数函数中,只保留最高阶项
    - 如果最高阶项系数存在且不是1,则去除与这个项相乘的常数。


    【普通递归实现】:

    #include<stdio.h>
    #include<Windows.h>
    
    long long fib(long long n){
        if(n < 3)
            return 1;
        return fib(n-1)+fib(n-2);
    }
    
    int main(){
        long long n = 0;
        scanf("%llu",&n);
        printf("%llu\n",fib(n));
        system("pause");
        return 0;
    }

    【时间复杂度】:O(2^n)

    这里写图片描述

    【空间复杂度】:O(n)

    这里写图片描述

    【缺陷】:重复计算次数太多,效率低下。


    【循环】:

    #include<stdio.h>
    #include<Windows.h>
    
    long long fib(long long n){
        int i = 0;
        long long first = 1,second = 1;
        long long ret = 0;
        for(i=3;i<=n;++i){
            ret = first + second;
            first = second;
            second = ret;
        }
        return second;
    }
    
    int main(){
        long long n = 0;
        scanf("%llu",&n);
        printf("%llu\n",fib(n));
        system("pause");
        return 0;
    }

    【时间复杂度】:O(n)
    【空间复杂度】:O(1)


    【升级版递归】:

    #include<stdio.h>
    #include<Windows.h>
    
    long long fib(long long first,long long second,long long n){
        if(n < 3)
            return 1;
        if(n == 3)
            return first + second;
        return fib(second,first+second,n-1);
    }
    
    int main(){
        long long n = 0;
        scanf("%llu",&n);
        printf("%llu\n",fib(1,1,n));
        system("pause");
        return 0;
    }

    【分析】:

    本算法采用了尾递归的算法;

    这里写图片描述

    【时间复杂度】:O(n)

    【空间复杂度】:O(n) (在VS debug环境下,其他环境有可能会进行编译器优化)

    【注意】:尾递归有时候在特定环境下会产生编译器优化,即不会再为尾递归函数调用下一级函数时开辟新栈,而是直接在旧函数的内存块上进行修改),这时它的空间复杂度为O(1)

    展开全文
  • 斐波那契数列时间复杂度O(logN)

    千次阅读 2018-12-29 02:50:29
    斐波那契数列时间复杂度O(logN) 解题思路: 把动态规划转化为矩阵的n次乘法,矩阵的n次乘法等价于计算一个数的n次方,把幂次转化为二进制数,转化为累乘,计算结果 public static void main(String[] args) { ...
  • 斐波那契数的时间复杂度、空间复杂度详解

    万次阅读 多人点赞 2018-05-26 01:00:21
    斐波那契数:斐波那契数列指的是1、1、2、3、5、8、13、21、······这样一个数列,我们可以发现它后面的一个数是前两个数之和。而在这个数列中的数就被称为斐波那契数。时间复杂度时间复杂度实际就是一个...
  • 斐波那契数列的三种解法及时间复杂度

    万次阅读 多人点赞 2017-12-12 08:50:54
    斐波那契数列
  • (算法的复杂性体现在运行该算法时的计算机所需资源的多少上,计算机资源最重要的是时间和空间(即寄存器)资源,因此复杂度分为时间和空间复杂度)。 如:for(int i=1;i;++i) // (1) 该语句时间复杂度:1+n+n  for...
  • 一、斐波那契数列的定义 二 、递归实现 三、循环实现 四、补充 一、斐波那契数列的定义 二 、递归实现 经典例题(杭电2041): AC代码: #include <iostream> using namespace std; int f[41]; ...
  • 斐波那契数列_详解(C语言)

    万次阅读 多人点赞 2020-05-06 15:25:56
    斐波那契数列Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、...
  • 一:递归实现  使用公式f[n]=f[n-1]+f[n-2],依次递归计算... 当然队列比数组更适合实现斐波那契数列时间复杂度和空间复杂度和vector一样,但队列太适合这里了,  f(n)=f(n-1)+f(n-2),f(n)只和f(n-1)和f(n-2)有关
  • c语言 时间复杂度和空间复杂度

    千次阅读 2019-04-27 12:46:09
    一是时间效率(时间复杂度),二是空间效率(空间复杂度) 什么是时间复杂度? 在计算机科学中,算法的时间复杂度是一个函数,他定量描述了该算法的运行 时间. 时间复杂度为什么不使用时间来衡量而使用基本语句...
  • 1、在学习数据结构这门课的过程中,发现斐波那契数列的递归算法以及非递归算法,以及其时间复杂度分析是一个小难点。所以特别总结一下。 斐波那契数列的表达式: Fibonacci数列简介: F(1)=1 F(2)=1 F(n)=F(n-...
  • C语言斐波那契数列四种优化求解

    万次阅读 多人点赞 2018-08-19 00:22:40
    题目: 使用递归和非递归的方法分别实现求第n个斐波那契数,那么什么是斐波那契数。斐波那契数列指的是这样一个数列:0 、1、1、2、3、5、8、13、21...//时间复杂度O(N^2) //空间复杂度o(N) long long fi...
  • 在做编程题目的时候经常会遇到“斐波那契数列”相关的题目,尤其在做OJ中。下面说一些方法:(一)递归递归是最慢的会发生重复计算,时间复杂度成指数级。long long fac(int n){if(n==1) return 1;else if(n==2) ...
  • 斐波那契数列的几种求解方式和复杂度分析

    万次阅读 多人点赞 2018-01-18 16:40:36
    实现求解斐波那契数列的几种算法以及复杂度的比较
  • 迭代 效率最高,时间复杂度O(n),空间复杂度是O(1) 1: //迭代实现 2: public static int Fib2(int n) 3: { 4: if (n ) 5: { 6: return 1; 7: } 8: else 9: { 10: int first = 1; 11: int second = 1; 12: int temp =...
  • 动态规划 用于求解最优化子问题的,往往是高效的而准确的。这背后的逻辑,其实就是程序设计的最基本原理——不要让程序做重复的事情。一句话说算法对于一个复杂的问题,可以分解成若干...斐波那契数列大学课堂上,...
  • 该楼层疑似违规已被系统折叠隐藏此楼查看此楼k阶斐波那契数列的第k项的值。常见的是2阶斐波那契数列。例如:f[n]=f[n-1]+f[n-2]+f[n-3]是三阶。矩阵二分算法如下(JAVA代码,大数运算):importjava.math.BigInteger;...
  • 斐波那契数列的三种算法以及复杂度

    万次阅读 多人点赞 2017-12-20 22:48:57
    斐波那契数列: f(n)=f(n-1)+f(n-2)(n>2) f(0)=1;f(1)=1; 即有名的兔子繁衍问题 在本篇文章我将会给出三种解法 递归 (1)递归:函数自己调用自己 (2)递归的"缺陷":递归到一定程度,会发生"栈溢出" (3...
  • C语言斐波那契数列

    2020-08-10 09:48:30
    一.递归算法 #define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> int fib(int k) { if (k <= 2) ... printf("求输入斐波那契数列的阶数"); scanf("%d", &n); res=fib(n); prin
  • 实验内容: ①利用多种方法实现斐波那契数列分别可用循环,递归和分治3种方法,并由此估算三种算法的时间复杂度,比较三种算法的运行效率。 ②首先定义主函数分别定义3个时间变量来作为三种算法的运行时间,并且在...
  • 斐波拉契数列的实现和时间复杂度的分析算是一个难点,在考研数据结构中也经常会碰到,今天我们就来仔细分析下和解决掉这个问题。 1. 首先,我们先来看看递归形式斐波拉契数列C语言实现: # include<stdio.h>...
  • 斐波那契数列说起

    2021-05-22 14:18:03
    这段时间在看算法相关的一些东西;因为算法不好连笔试都过不了(哭,其实算法...斐波那契数列今天看到斐波那契数列感觉很有意思; 斐波那契数列:f(0) = 0;f(1) = 1;f(n) = f(n-1) + f(n-2) n>2;嗯,不是很复杂,...
  • C斐波那契数列两种解法对比(递归与循环)什么是斐波那契数列斐波那契数列的算法(递归)斐波那契数列(递归)の缺点递归的优点再来看看...百度百科比较专业的说法是:斐波那契数列Fibonacci sequence),又称...
  • C语言)数据结构——时间复杂度、空间复杂度

    多人点赞 热门讨论 2021-08-20 22:34:54
    算法的复杂度二、时间复杂度2.1.什么是时间复杂度?2.2.大O的渐进表示法2.3.常见时间复杂度的分析三、空间复杂度3.1.什么是空间复杂度?2.1.常见空间复杂度的分析总结 前言 提示:这里可以添加本文要记录的大概内容...
  • 目录写在前面本节目标基本概念**常见算法的时间复杂度计算**时间复杂度对比常见空间复杂度计算有复杂度的算法练习题 本节目标 1.什么是时间复杂度和空间复杂度? 2.如何计算常见算法的时间复杂度和空间复杂度? 3....
  • 在做编程题目的时候经常会遇到“斐波那契数列”相关的题目,尤其在做OJ中。下面说一些方法:(一)递归递归是最慢的会发生重复计算,时间复杂度成指数级。复制代码 代码如下:long long fac(int n){if(n==1) return 1;...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,982
精华内容 792
关键字:

斐波那契数列c语言时间复杂度

c语言 订阅