精华内容
下载资源
问答
  • 只懂得了点意思,具体怎么计算空间复杂度我现在也还不懂,先慢慢完善吧……求高人指点!!! 空空间复杂度 类似于时间复杂度的讨论,一个算法的空间复杂度(SpaceComplexity)S(n)定义为该算法所耗费的存储空间,...

    只懂得了点意思,具体怎么计算的空间复杂度我现在也还不懂,先慢慢完善吧……求高人指点!!!

    空空间复杂度

    类似于时间复杂度的讨论,一个算法的空间复杂度(SpaceComplexity)S(n)定义为该算法所耗费的存储空间,它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。空间复杂度(SpaceComplexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间,算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的,是通过参数表由调用函数传递而来的,它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比,要压缩这方面的存储空间,就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异,有的算法只需要占用少量的临时工作单元,而且不随问题规模的大小而改变,我们称这种算法是“就地\"进行的,是节省存储的算法,如这一节介绍过的几个算法都是如此;有的算法需要占用的临时工作单元数与解决问题的规模n有关,它随着n的增大而增大,当n较大时,将占用较多的存储单元,例如将在第九章介绍的快速排序和归并排序算法就属于这种情况。
    分析一个算法所占用的存储空间要从各方面综合考虑。如对于递归算法来说,一般都比较简短,算法本身所占用的存储空间较少,但运行时需要一个附加堆栈,从而占用较多的临时工作单元;若写成非递归算法,一般可能比较长,算法本身占用的存储空间较多,但运行时将可能需要较少的存储单元。
    一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小,它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。若一个算法为递归算法,其空间复杂度为递归所使用的堆栈空间的大小,它等于一次调用所分配的临时存储空间的大小乘以被调用的次数(即为递归调用的次数加1,这个1表示开始进行的一次非递归调用)。算法的空间复杂度一般也以数量级的形式给出。如当一个算法的空间复杂度为一个常量,即不随被处理数据量n的大小而改变时,可表示为O(1);当一个算法的空间复杂度与以2为底的n的对数成正比时,可表示为O(log2n);当一个算法的空I司复杂度与n成线性比例关系时,可表示为O(n).若形参为数组,则只需要为它分配一个存储由实参传送来的一个地址指针的空间,即一个机器字长空间;若形参为引用方式,则也只需要为其分配存储一个地址的空间,用它来存储对应实参变量的地址,以便由系统自动引用实参变量。

    3时间与空间复杂度比较

    对于一个算法,其时间复杂度空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时,可能会使空间复杂度的性能变差,即可能导致占用较多的存储空间;反之,当追求一个较好的空间复杂度时,可能会使时间复杂度的性能变差,即可能导致占用较长的运行时间。另外,算法的所有性能之间都存在着或多或少的相互影响。因此,当设计一个算法(特别是大型算法)时,要综合考虑算法的各项性能,算法的使用频率,算法处理的数据量的大小,算法描述语言的特性,算法运行的机器系统环境等各方面因素,才能够设计出比较好的算法。算法的时间复杂度和空间复杂度合称为算法的复杂度。
    具体计算如下:(待完善中)

    展开全文
  • 忽略常数,用O(1)表示递归算法的空间复杂度=递归深度N*每次递归所要的辅助空间对于单线程来说,递归有运行时堆栈,求的是递归最深的那一次压栈所耗费的空间的个数,因为递归最深的那一次所耗费的空间足以容纳它所有...

    首先要明确一个概念,变量的内存分配发生在定义的时候

     

     忽略常数,用O(1)表示 
    递归算法的空间复杂度=递归深度N*每次递归所要的辅助空间 
    对于单线程来说,递归有运行时堆栈,求的是递归最深的那一次压栈所耗费的空间的个数,因为递归最深的那一次所耗费的空间足以容纳它所有递归过程。
    a = 0
    b = 0
    print(a,b)
    它的空间复杂度O(n)=O(1);

    def fun(n):
    k = 10
    if n == k:
    return n
    else:
    return fun(++n)
    递归实现,调用fun函数,每次都创建1个变量k。调用n次,空间复杂度O(n*1)=O(n)。

    for(i=0;i<n;++):
    temp = i
     变量的内存分配发生在定义的时候,因为temp的定义是循环里边,所以是n*O(1)

    temp=0;
    for(i=0;i<n;i++):
    temp = i
    temp定义在循环外边,所以是1*O(1) 
    ---------------------
    作者:qq_17534301
    来源:CSDN
    原文:https://blog.csdn.net/qq_17534301/article/details/82872357
    版权声明:本文为博主原创文章,转载请附上博文链接!

    转载于:https://www.cnblogs.com/wonker/p/11238418.html

    展开全文
  • 前言: 时间复杂度是执行算法的时间成本,空间复杂度是执行算法的空间成本。 人们之所以花大力气去评估算法的时间复杂度和空间复杂度,其根本原因是计算机的运行速度和空间都是有限的。 在运行一段程序时,不仅要...

    前言: 时间复杂度是执行算法的时间成本,空间复杂度是执行算法的空间成本。

    人们之所以花大力气去评估算法的时间复杂度和空间复杂度,其根本原因是计算机的运行速度和空间都是有限的。

    在运行一段程序时,不仅要执行各种运算指令,同时还需要存储临时的中间数据,以便后面的程序可以继续执行。

    怎么样才能提高算法的效率呢?这种情况下,必须使用到一些中间数据啦。

    内存空间是有限的,在时间复杂度相同的情况下,算法占用的内存空间越小越好。如何描述一个空间占用的内存空间的大小呢?这就用到了算法的另一个指标,空间复杂度。

    基本概念了解啦,如何计算空间复杂度呢?

    常见的空间复杂度有以下几种:
    1.常量空间

    当算法的存储空间大小固定,和输入的规模没有直接联系,空间复杂度记作O(1),例如下面这段程序:

    void fun1(int n)
    {
    int var =3;
    }

    2 线性空间

    当算法分配的空间是一个线性的集合,并且集合大小和输入规模n成正比。空间复杂度记作O(n),例如下面这段程序:

    void fun2(int n)
    {
    int array[] = new int[n];
    }

    3二维空间
    当算法分配的集合是一个二维数组集合,并且集合的长度和宽度与输入的n成正比关系,空间复杂度记作O(n*n),例如下面这段程序:

    void fun3(int n)
    {
    int matrix[] = new int[n][n];
    }
    4 递归空间
    递归是一种比较特殊的场景,虽然递归代码没有显式地声明变量和集合,但是计算机在执行程序时,会专门分配一块内存,用来存储:“方法调用栈”
    void fun4(int n)
    {
    if(n<=1)
    {
    return;
    }
    fun4(n-1);
    }
    最终,方法调用栈的全部元素都会一一出栈。
    由上面可以看出,执行递归操作所需的内存空间和递归深度成正比。如果递归的深度是n,那么空间复杂度就是O(n)

    展开全文
  • 关于计算时间复杂度和空间复杂度

    万次阅读 多人点赞 2016-09-04 00:09:45
    相信学习编程的同学,或多或少都接触到算法的时间复杂度和空间复杂度了,那我来讲讲怎么计算。  常用的算法的时间复杂度和空间复杂度 一,求解算法的时间复杂度,其具体步骤是:  ⑴ 找出算法中的基本语句;  ...

            相信学习编程的同学,或多或少都接触到算法的时间复杂度和空间复杂度了,那我来讲讲怎么计算。

           常用的算法的时间复杂度和空间复杂度 一,求解算法的时间复杂度,其具体步骤是:

      ⑴ 找出算法中的基本语句;

      算法中执行次数最多的那条语句就是基本语句,通常是最内层循环的循环体。

      ⑵ 计算基本语句的执行次数的数量级;

      只需计算基本语句执行次数的数量级,这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可,可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析,并且使注意力集中在最重要的一点上:增长率。

      ⑶ 用大O记号表示算法的时间性能。

      将基本语句执行次数的数量级放入大O记号中。

      如果算法中包含嵌套的循环,则基本语句通常是最内层的循环体,如果算法中包含并列的循环,则将并列循环的时间复杂度相加。例如:

      for (i=1; i<=n; i++)
      x++;

      for (i=1; i<=n; i++)
      for (j=1; j<=n; j++)
      x++;

      第一个for循环的时间复杂度为O(n),第二个for循环的时间复杂度为O(n2),则整个算法的时间复杂度为O(n+n2)=O(n2)。

      常见的算法时间复杂度由小到大依次为:

      O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<…<O(2n)<O(n!)

    Ο(1)表示基本语句的执行次数是一个常数,一般来说,只要算法中不存在循环语句,其时间复杂度就是O(1)。O(log2n)、O(n)、O(nlog2n)、O(n2)和O(n3)称为多项式时间,而O(2n)和O(n!)称为指数时间。计算机科学家普遍认为前者是有效算法,把这类问题称为P(Polynomial,多项式)类问题,而把后者称为NP(Non-Deterministic Polynomial,非确定多项式)问题。

    在计算算法时间复杂度时有以下几个简单的程序分析法则: 
       (1).对于一些简单的输入输出语句或赋值语句,近似认为需要O(1)时间 
       (2).对于顺序结构,需要依次执行一系列语句所用的时间可采用大O下"求和法则" 求和法则:是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1(n)+T2(n)=O(max(f(n),g(n)))。特别地,若T1(m)=O(f(m)), T2(n)=O(g(n)),则 T1(m)+T2(n)=O(f(m)+g(n)) 
       (3).对于选择结构,如if语句,它的主要时间耗费是在执行then字句或else字句所用的时间,需注意的是检验条件也需要O(1)时间 
       (4).对于循环结构,循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费,一般可用大O下"乘法法则" 
    乘法法则: 是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1*T2=O(f(n)*g(n)) 
       (5).对于复杂的算法,可以将它分成几个容易估算的部分,然后利用求和法则和乘法法则技术整个算法的时间复杂度 
       另外还有以下2个运算法则:(1) 若g(n)=O(f(n)),则O(f(n))+O(g(n))=O(f(n));(2)O(Cf(n)) = O(f(n)),其中C是一个正常数。

    几个常见的时间复杂度进行示例说明

    (1)、O(1) 

     Temp=i; i=j; j=temp;                     
       以上三条单个语句的频度均为1,该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶,记作T(n)=O(1)。注意:如果算法的执行时间不随着问题规模n的增加而增长,即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。 

    (2)、O(n2)

    交换i和j的内容

    1.sum=0;(一次)   

    2.for(i=1;i<=n;i++) (n+1次)   

    3.for(j=1;j<=n;j++)(n(n+1)次)   

    4.sum++;(n(n+1)+1次) 

    因为(2n2+n+1)=n2(即:去低阶项,去掉常数项,去掉高阶项的常参得到),所以T(n)= =O(n2);

    一般情况下,对步进循环语句只需考虑循环体中语句的执行次数,忽略该语句中步长加1、终值判别、控制转移等成分,当有若干个循环语句时,算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。

    (3)、O(n)  

    1.a=0;   

    2.b=1;               ①   

    3.for (i=1;i<=n;i++) ②   

    4.{s=a+b;            ③   

    6.b=a;               ④     

    7.a=s; }             ⑤ 

    语句1的频度为2,语句2的频度为n,语句3的频度为n-1,语句4的频度为n-1,语句5的频度为n-1, 即T(n)=2+n+3(n-1)=4n-1=O(n). 

    (4)、O(log2n) 

    1. i=1;   ①   

    2. while (i<=n)   

    3. i=i*2; ② 

    语句1的频度是1,设语句2的频度是f(n),则:2^f(n)<=n;f(n)<=log2n,取最大值f(n)=log2n,即T(n)=O(log2n) 

    (5)、O(n3)  

    1. for(i=0;i<n;i++){     

    2. for(j=0;j<i;j++){   

    3.for(k=0;k<j;k++)   

    4.x=x+2; }}

    当i=m,j=k的时候,内层循环的次数为k当i=m时, j可以取 0,1,...,m-1 ,所以这里最内循环共进行了0+1+...+m-1=(m-1)m/2次所以,i从0取到n,则循环共进行了:0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以时间复杂度为O(n3).

    二,算法的空间复杂度:

    类似于时间复杂度的讨论,一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间,它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间算法的输入输出数据所占用的存储空间算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的,是通过参数表由调用函数传递而来的,它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比,要压缩这方面的存储空间,就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异,有的算法只需要占用少量的临时工作单元,而且不随问题规模的大小而改变,我们称这种算法是“就地\"进行的,是节省存储的算法,如这一节介绍过的几个算法都是如此;有的算法需要占用的临时工作单元数与解决问题的规模n有关,它随着n的增大而增大,当n较大时,将占用较多的存储单元。

    当一个算法的空间复杂度为一个常量,即不随被处理数据量n的大小而改变时,可表示为O(1);当一个算法的空间复杂度与以2为底的n的对数成正比时,可表示为0(10g2n);当一个算法的空间复杂度与n成线性比例关系时,可表示为0(n).若形参为数组,则只需要为它分配一个存储由实参传送来的一个地址指针的空间,即一个机器字长空间;若形参为引用方式,则也只需要为其分配存储一个地址的空间,用它来存储对应实参变量的地址,以便由系统自动引用实参变量。

    算法的空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度的计算公式记作:S(n)= O(f(n)),其中,n为问题的规模,f(n)为语句关于n所占存储空间的函数。

    一般情况下,一个程序在机器上执行时,除了需要存储程序本身的指令、常数、变量和输入数据外,还需要存储对数据操作的存储单元。若输入数据所占空间只取决于问题本身,和算法无关,这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常数,则称此算法为原地工作,空间复杂度为O(1)。关于O(1)的问题, O(1)是说数据规模和临时变量数目无关,并不是说仅仅定义一个临时变量。举例:无论数据规模多大,我都定义100个变量,这就叫做数据规模和临时变量数目无关。就是说空间复杂度是O(1)。

    对于一个算法,其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时,可能会使空间复杂度的性能变差,即可能导致占用较多的存储空间;反之,求一个较好的空间复杂度时,可能会使时间复杂度的性能变差,即可能导致占用较长的运行时间。另外,算法的所有性能之间都存在着或多或少的相互影响。因此,当设计一个算法(特别是大型算法)时,要综合考虑算法的各项性能,算法的使用频率,算法处理的数据量的大小,算法描述语言的特性,算法运行的机器系统环境等各方面因素,才能够设计出比较好的算法。

    常用的算法的时间复杂度和空间复杂度


    一个经验规则:其中c是一个常量,如果一个算法的复杂度为c 、 log2n 、n 、 n*log2n ,那么这个算法时间效率比较高 ,如果是2n ,3n ,n!,那么稍微大一些的n就会令这个算法不能动了,居于中间的几个则差强人意。 
           算法复杂度分析是一个很重要的问题,任何一个程序员都应该熟练掌握其概念和基本方法,而且要善于从数学层面上探寻其本质,才能准确理解其内涵。


    展开全文
  • 已经在网上查了两天关于空间复杂度的内容了,发现答案几乎都是很笼统的,可以举例说明如何计算空间复杂度吗?
  • 一、算法的时间复杂度定义在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间量度。记作:T(n)=O(f(n))。它表示随...
  • 相信学习编程的同学,或多或少都接触到算法的时间复杂度和空间复杂度了,那我来讲讲怎么计算。  常用的算法的时间复杂度和空间复杂度 一,求解算法的时间复杂度,其具体步骤是:  ⑴ 找出算法中的基本语句; ...
  • 学习算法我们首先需要清楚的概念就是时间复杂度和空间复杂度接下来我们就详细讲解一下时间复杂度和空间复杂度,为大家后面的学习打好基础!算法入门书籍挑选点下方链接:小乔甜甜:算法入门书籍该怎么选?快速找到最...
  • 明白怎么来算时间、空间复杂度。 常见的时间、空间复杂度。 1.谈谈对时间、空间复杂度的理解 时间复杂度:描述算法中语句的执行次数,评估该算法执行所需的时间。 空间复杂度:描述一个程序所需内存的大小,评估该...
  • 那就要用到【时间复杂度】和【空间复杂度】了,评判算法好坏的主要两个维度。1、何为复杂度什么是【时间复杂度】和【空间复杂度】呢?顾名思义,一个是代表算法执行消耗的时间,一个代表算法执行消耗的空间。在...
  • 相信学习编程的同学,或多或少都接触到算法的时间复杂度和空间复杂度了,那我来讲讲怎么计算。  常用的算法的时间复杂度和空间复杂度 一,求解算法的时间复杂度,其具体步骤是:  ⑴ 找出算法中的基本语句...
  • 而在实际衡量时,我们通常会围绕以下2 个维度进行:时间复杂度和空间复杂度。 2.如何去计算复杂度? 复杂度是一个关于输入数据量 n 的函数。假设你的代码复杂度是 f(n),那么就用个大写字母 O 和括号,把 f(n) 括...
  • 6.怎么在时间复杂度O(1),空间复杂度O(1)下计算斐波那契数 1.斐波那契数简介 斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家莱昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而...
  • 而在证明算法是正确的基础上,第二部就是分析算法的时间复杂度。算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级,在很大程度上能很好反映出算法的优劣与否。因此,作为程序员,掌握基本的算法时间...
  • 定义: 时间复杂度是指执行算法所需要的计算工作量 话不多说,直接上图: 一个算法中的语句执行次数称为 语句频度或时间频度。记为T(n)。 第一个:T(n) = 2; 第二个:T(n) = 3n+3; 缺点:当代码量越来越大的...
  • 刚接触空间复杂度的时候,可能很多人知道什么是空间复杂度,但是往往不知道怎么计算。 和时间复杂度类似,空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量,也是使用大O表示法。 1、常量空间 存储...
  • 而在证明算法是正确的基础上,第二部就是分析算法的时间复杂度。算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级,在很大程度上能很好反映出算法的优劣与否。因此,作为程序员,掌握基本的算法时间...
  • 算法核心——空间复杂度和时间复杂度超详细解析一、什么是算法算法:一个有限指令集接受一些输入(有些情况下不需要收入)产生输出一定在有限步骤之后终止每一条指令必须:有充分明确的目标,不可以有歧义计算机能处理...
  • 算法初级-----时间复杂度与空间复杂度的计算 什么是算法? 算法,对应的英文单词是algoriithm 算出1+2+3+4+6+7…一直加到10000的结果,怎么计算呢? 老师以为,熊孩子会按部就班地一步一步计算,就像下面这样。 1+2...
  • 相信学习编程的同学,或多或少都接触到算法的时间复杂度和空间复杂度了,那我来讲讲怎么计算。 常用的算法的时间复杂度和空间复杂度 一,求解算法的时间复杂度,其具体步骤是:  ⑴ 找出算法中的基本语句;  ...
  • 时/空间复杂度

    2019-11-10 20:44:18
    怎么计算时间复杂度 我们计算时间复杂度,并不一定要计算所有执行次数,而是择其大概次数就行了。 即渐进计数。 渐进计数就是说 1 已知常数次记为O(1); 2 忽略 系数 即2N次 记为O(n); 3 大数据下忽略小数据 即 N^2+...
  • 需要引入一个衡量的标准(metric)—时间复杂度和空间复杂度。 学习数据结构和算法的基石,就是要学会复杂度分析。知道怎么去分析复杂度,才能作出正确的判断,在特定的场景下选用合适的正确的算法。而不是盲目的死记...
  • 算法:为了解决一个问题,你...时间复杂度主要衡量的就是算法的运行速度,而空间复杂度主要衡量的就是一个算法所需要的一个额外空间。 时间复杂度 算法的时间复杂度是一个函数基本总的执行次数,也就是一个算法...

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 179
精华内容 71
关键字:

怎么计算空间复杂度