空间复杂度 订阅
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了,因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。 展开全文
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了,因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。
信息
记    做
S(n)=O(f(n))。
衡    量
执行时间和所需要占用的存储空间
中文名
空间复杂度
外文名
space complexity
空间复杂度量度简介
类似于 [1]  时间复杂度的讨论,一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间,它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。空间复杂度(SpaceComplexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间,算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的,是通过参数表由调用函数传递而来的,它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比,要压缩这方面的存储空间,就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异,有的算法只需要占用少量的临时工作单元,而且不随问题规模的大小而改变,我们称这种算法是“就地\"进行的,是节省存储的算法,有的算法需要占用的临时工作单元数与解决问题的规模n有关,它随着n的增大而增大,当n较大时,将占用较多的存储单元,例如快速排序和归并排序算法就属于这种情况。
收起全文
精华内容
参与话题
问答
  • 时间复杂度和空间复杂度的概念及各种算法的时间复杂度 及举例 算法的复杂度可分为俩种 一种时间复杂度 另一种是空间复杂度。 俩者的概念:时间复杂度是指执行这个算法所需要的计算工作量;而空间复杂度是指执行这个...

    时间复杂度和空间复杂度的概念及各种算法的时间复杂度 及举例

    算法的复杂度可分为俩种 一种时间复杂度 另一种是空间复杂度。

    俩者的概念:时间复杂度是指执行这个算法所需要的计算工作量;而空间复杂度是指执行这个算法所需要的内存空间。时间和空间(即寄存器)都是计算机资源的重要体现,而算法的复杂性就是体现在运行该算法时的计算机所需的资源多少

    各种算法的复杂度如下:
    在这里插入图片描述
    时间复杂度:

    1:算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级,在很大程度上能很好地反映出算法的优劣与否;

    2:算法执行时间需要依据该算法编制的程序在计算机上执行运行时所消耗的时间来度量,度量方法有两种,事后统计方法和事前分析估算方法,因为事后统计方法更多的依赖计算机的硬件,软件等环境因素,有时容易掩盖算法本身的优劣。因此常常采用事前分析估算的方法;

    3:一个算法是由控制结构(顺序,分支,循环三种)和原操作(固有数据类型的操作)构成的,而算法时间取决于两者的综合效率;

    4:一个算法花费的时间与算法中语句的执行次数成正比,执行次数越多,花费的时间就越多。一个算法中的执行次数称为语句频度或时间频度。记为T(n);

    5:在时间频度中,n称为问题的规模,当n不断变化时,它所呈现出来的规律,我们称之为时间复杂度(其实在这中间引入了一个辅助函数f(n),但它与t(n)是同数量级函数,我们且先这样理解。)

    6:在各种算法中,若算法中的语句执行次数为一个常数,则时间复杂度为o(1);同时,若不同算法的时间频度不一样,但他们的时间复杂度却可能是一样的,eg:T(n)=n^2+2n+4 与 T(n)=4n2+n+8,他们的时间频度显然不一样,但他们的时间复杂度却是一样的,均为O(n2),时间复杂度只关注最高数量级,且与之系数也没有关系。

    7: 求解算法的时间复杂度的具体步骤是:
      ⑴ 找出算法中的基本语句;
      算法中执行次数最多的那条语句就是基本语句,通常是最内层循环的循环体。
      ⑵ 计算基本语句的执行次数的数量级;
      只需计算基本语句执行次数的数量级,这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可,可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析,并且使注意力集中在最重要的一点上:增长率。
      ⑶ 用大Ο记号表示算法的时间性能。
      将基本语句执行次数的数量级放入大Ο记号中。
      如果算法中包含嵌套的循环,则基本语句通常是最内层的循环体,如果算法中包含并列的循环,则将并列循环的时间复杂度相加
    下面我来举一个简单例子:

    for(i=1;i<=n;i++)
    {a++};
    for(i=1;i<=n;i++)
    {
    for(j=1;j<=n;j++)
    {
    a++;
    }
    }
    第一个for循环的时间复杂度为o(n),第二个for循环时间复杂度为o(n2),则整个算法的时间复杂度为o(n2+n)。
    o(1)表示基本语句的执行次数是一个常数,一般来说,只要算法中不存在循环语句,时间复杂度就为o(1)。

    空间复杂度(Space Complexity):

    1:空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度;

    2:一个算法在计算机上占用的内存包括:程序代码所占用的空间,输入输出数据所占用的空间,辅助变量所占用的空间这三个方面,程序代码所占用的空间取决于算法本身的长短,输入输出数据所占用的空间取决于要解决的问题,是通过参数表调用函数传递而来,只有辅助变量是算法运行过程中临时占用的存储空间,与空间复杂度相关;

    3:通常来说,只要算法不涉及到动态分配的空间,以及递归、栈所需的空间,空间复杂度通常为0(1);

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

    展开全文
  • 时间复杂度和空间复杂度

    千次阅读 2019-11-11 19:28:12
    前段时间在学数据结构的时候,就提到过关于时间复杂度和空间复杂度的,当时就想,还有什么是计算机算不出来的,就觉得这东东很水 ,事实上确实有那么一点点水,但是这几天在刷题的时候,发现有些题后面对程序的时间...

    时间复杂度和空间复杂度
    前段时间在学数据结构的时候,就提到过关于时间复杂度和空间复杂度的,当时就想,还有什么是计算机算不出来的,就觉得这东东很水 ,事实上确实有那么一点点水,但是这几天在刷题的时候,发现有些题后面对程序的时间复杂度和空间复杂度还有要求,什么时间复杂度为O(N),空间复杂度为O(1)什么的,想想这块还是整理一下的好。,
    首先,平常我们做一件事,我们总是在想有没有更好的方法,可不可以少做点什么而不影响结果的,其实还是懒 ,就像上课的时候,从宿舍楼到教室,总是在想有没有一条最近的路,可以省时间的(时间复杂度),下课的时候,又在想有没有哪一条路的人少一点,顺畅一些,可以更快的离开(空间复杂度)。。。。总的来说,还是离不开两个字–>效率。
    时间复杂度
    同样的,计算机也有效率这个概念,平时在运行代码的时候,计算机跑的飞快,很难判断两个算法的快慢,那么C语言里Sleep这个函数就可以判断下了,作用就是让程序在运行期间睡个觉,跑慢一点,这样的话,两个时间复杂度不同的代码,快慢就显示出来了,好坏立见;计算机跑的那么快,执行速度都是每毫秒多少数据的那种,那么宏观上用执行时间来判断算法的好坏有点小困难,这时候就从微观上入手,一个算法所花费的时间与其中语句的执行次数成正比的关系,以算法的执行次数来算时间,执行多少次,他的时间复杂度就是多少就显得很直观。

    void Func1(int N)
    {
    	int count = 0;
    	for (int i = 0; i < N ; ++ i)
    	{
    		for (int j = 0; j < N ; ++ j)
     		{
    			++count;
    		 }
    	}
    	for (int k = 0; k < 2 * N ; ++ k) 
    	{
    		++count;
    	}
    	int M = 10;
    	while (M--) 
    	{
    		++count; 
    	}
    	printf("%d\n", count);
    }
    

    直观上看,算法的执行次数 F(N)=N^2+2*N+10 *但是真正表示算法的时间复杂度的时候,却没有见到过有这么具体的数字,都是O(N),O(N ^2),为什么会这样呢,同是O(N)的时间复杂度,他们的执行次数真的一样吗?先打个比方,假如你是一个亿万富翁,去买一瓶矿泉水~~(不考虑为什么买的是矿泉水 )~~ ,会不会给店家说找99块钱,应该不会吧,估摸着他等店家找钱的时间,已经可以赚回来好几倍的99了。。。。。同样的,时间复杂度的计算也是如此,N^2和2**N,看起来好像差别不大,但是当N非常大的时候,前者比后者就大很多了,时间复杂度表示的只是一个大概的次数,把执行次数写的具体一点的话,就显得有点不好了,这个时候往往选择以偏概全,选择最大的一个执行次数,即大O的渐进表示法。上面所示的时间复杂度即为O(N ^2)。

    到了我们最熟悉的冒泡排序法了

    void sort(int* a,int len)
    {
        int i=0;
        int j=0;
        for(i=1;i<len;i++)
        {
        	int flag=1;
            for(j=0;j<len-i;j++)
            {
                if(a[j]>a[j+1])
                {
                    int t=a[j];
                    a[j]=a[j+1];
                    a[j+1]=t;
                    flag=0;
                }
            }
            if(flag==1)
            {
                break;
            }
        }
    }
    

    通常来说,运气好一点的话,冒泡排序的时间复杂度就是O(N),运气不好就是O(N ^2)。。。。。表示一个算法的时间复杂度应该如何选择呢,肯定不能选最好的情况,这时候以偏概全就显得不是那么的好,只能用最坏的情况来代表算法真正的时间复杂度。

    二分查找呢(两种二分查找的方式)

    //[left,right]
    int BinarySearch(int* a, int left, int right, int x)
    {
    	while (left <= right)
    	{
    		int mid = (left + right) / 2;
    		if (a[mid] == x)
    		{
    			return mid;
    		}
    		else if (a[mid] > x)
    		{
    			right = mid + 1;
    		}
    		else
    		{
    			left = mid - 1;
    		}
    	}
    	return -1;
    }
    
    
    //[left,right)
    int BinarySearch2(int* a, int left, int right, int x)
    {
    	while (left < right)
    	{
    		int mid = (left + right) / 2;
    		if (a[mid] == x)
    		{
    			return mid;
    		}
    		else if (a[mid] > x)
    		{
    			right = mid;
    		}
    		else
    		{
    			left = mid+1;
    		}
    	}
    	return -1;
    }
    
    

    怎么说呢,运气最好的情况就是要找的数就在中间,一次到位,但是表示肯定不能这样来,因为不能保证没一次都中奖吧,二分查找的时间复杂的O(log2 N) log以2为底 N的对数次(表示数学都还给老师了一时间没看明白这什么意思 )

    还有以前的数学题,斐波那契数的递归算法

    int Fibonacci(int num)
    {
    	if(num<3)
    	{
    		return 1;
    	}
    	return Fibonacci(num-1)+Fibonacci(num-2);
    }
    

    简单的斐波那契数
    简单的一个斐波那契数,用递归写真的正确吗,递归的内部就是一个树状的结构,他的每一个结果都是一步一步单独计算出来的,每一个结点都是一个单独的计算,既耗费时间还耗费空间,而且当要计算的数字大于50的时候,程序就会跑的比较慢了,不能立刻出结果的那种。递归的时间复杂度是O(N ^2)
    而递推就不一样了

    #include<stdio.h>
    
    int main()
    {
    	int f1 = 1, f2 = 1, f3 ;
    	int i = 0;
    	int num;
    	scanf("%d",&num);
    	for (i = 3; i <= num; i++)
    	{
    		f3= f1 + f2 ;
    		f1 = f2;
    		f2 = f3;
    	}
    	printf("%d", f3);
    	return 0;
    }
    

    递推的时间复杂度便是O(N),计算大数据明显比递归快很多。

    空间复杂度
    空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。
    一般来说,只要算法不涉及到动态分配空间,递归以及栈帧,空间复杂度都是O(1);

    给定一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,返回移除后数组的新长度。
    不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

    int removeElement(int* nums, int numsSize, int val){
        int i=0;
        int src=0;
        for(i=0;i<numsSize;i++)
        {
            if(nums[i]!=val)
            {
                nums[src]=nums[i];
                src++;
            }
        }
        return src;
    }
    

    给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素最多出现两次,返回移除后数组的新长度。
    不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

    int removeDuplicates(int* nums, int numsSize){
        int i=0;
        int len=0;
        int j=0;
        if(numsSize==0)
        {
            return 0;
        }
        for(i=0;i<numsSize-1;i++)
        {
            if(nums[i]==nums[i+1]&&(len<2))
            {
                nums[j]=nums[i];
                j++;
                len++;
            }
            if(nums[i]!=nums[i+1]&&(len<2))
            {
                nums[j]=nums[i];
                j++;
                len=0;
            }
            else if(nums[i]!=nums[i+1]&&(len>=2))
            {
                len=0;
            }
            
        }
        if(len<2)
        {
            nums[j]=nums[i];
            j++;
        }
        return j;
    }
    
    展开全文
  • 空间复杂度

    千次阅读 2019-05-10 18:15:52
    空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度,我们用 S(n) 来定义。 计算方法 1. 空间复杂度 O(1) 如果算法执行所需要的临时空间不随着某个变量n的大小而变化,即此算法空间复杂度为一个常量...

    基本概念

    空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度,我们用 S(n) 来定义。

    计算方法

    1. 空间复杂度 O(1)
    如果算法执行所需要的临时空间不随着某个变量n的大小而变化,即此算法空间复杂度为一个常量,可表示为 O(1)

    int i = 1;
    int j = 2;
    ++i;
    j++;
    int m = i + j;
    

    变量 i、j、m 所分配的空间都不随着处理数据量变化,因此它的空间复杂度 S(n) = O(1)

    2. 空间复杂度 O(n)

    int[] m = new int[n]
    for(i=1; i<=n; ++i)
    {
       j = i;
       j++;
    }
    

    这段代码中,第一行new了一个数组出来,这个数据占用的大小为n,这段代码的2-6行,虽然有循环,但没有再分配新的空间,因此,这段代码的空间复杂度主要看第一行即可,即 S(n) = O(n)

    转自:https://zhuanlan.zhihu.com/p/50479555

    展开全文
  • 常用的算法的时间复杂度和空间复杂度:   排序法 最差时间分析 平均时间复杂度 稳定度 空间复杂度 冒泡排序 O(n2) O(n2) 稳定 O(1) 快速排序 O(n2) O(n*log2n) 不稳定 O(log2n)~O(n) ...

     

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

      

    排序法

    最差时间分析 平均时间复杂度 稳定度 空间复杂度
    冒泡排序 O(n2) O(n2) 稳定 O(1)
    快速排序 O(n2) O(n*log2n) 不稳定 O(log2n)~O(n)
    选择排序 O(n2) O(n2) 稳定 O(1)
    二叉树排序 O(n2) O(n*log2n) 不一顶 O(n)

    插入排序

    O(n2) O(n2) 稳定 O(1)
    堆排序 O(n*log2n) O(n*log2n) 不稳定 O(1)
    希尔排序 O O 不稳定 O(1)

     

     

    时间复杂度:

    (1)时间频度 

           一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

           n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。

    (2)时间复杂度

          一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。 

          按数量级递增排列,常见的时间复杂度有:常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),..., k次方阶O(nk),指数阶O(2n)。

         算法中语句执行次数为一个常数,则时间复杂度为O(1)

    (3)时间复杂度的取值

       主要用算法时间复杂度的数量级评价一个算法的时间性能。

     

    时间复杂度的计算:

    1. 计算出基本操作的执行次数T(n) 
        基本操作即算法中的每条语句(以;号作为分割),语句的执行次数也叫做语句的频度。在做算法分析时,一般默认为考虑最坏的情况。

    2. 计算出T(n)的数量级 
        求T(n)的数量级,只要将T(n)进行如下一些操作:
        忽略常量、低次幂和最高次幂的系数
        令f(n)=T(n)的数量级。

    3. 用大O来表示时间复杂度 
        当n趋近于无穷大时,如果lim(T(n)/f(n))的值为不等于0的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))。

     

    一个示例: 
    int num1, num2;
    for(int i=0; i<n; i++){ 
         num1 += 1;
         for(int j=1; j<=n; j++){ 
             num2 += num1;
         }


    分析:
    1.
    语句int num1, num2;的频度为1;
    语句i=0;的频度为1;
    语句i<n; i++; num1+=1; j=1; 的频度为n;
    语句j<=n; j++; num2+=num1;的频度为n*n;
    T(n) = 2 + 4n + 3n*n

    2.
    忽略掉T(n)中的常量、低次幂和最高次幂的系数
    f(n) = n*n = n2

    3.
    T(n) = O(n2)

     

    空间复杂度:

    空间复杂度与时间复杂度类似,空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作: S(n)=O(f(n)) 我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。 

    空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间,算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。

    当一个算法的空间复杂度为一个常量,即不随被处理数据量n的大小而改变时,可表示为O(1)。

    展开全文
  • 快速理解时间复杂度与空间复杂度

    千次阅读 多人点赞 2018-05-11 17:48:05
    1.首先,时间复杂度与空间复杂度是对立的,时间复杂度越低,空间复杂度就越高。我们在程序中通常采用以空间换时间的方式来提高项目运行效率。 先给大家说一个最常见的简单的,时间复杂度是以n为变量,程序的运行次数...
  • 时间复杂度和空间复杂度的简单讲解

    万次阅读 多人点赞 2018-01-07 12:55:26
    文章最后,举例使用二分查找和斐波那契的递归和迭代方法,分别说明时间和空间复杂度。 时间复杂度: 首先要说的是,时间复杂度的计算并不是计算程序具体运行的时间,而是算法执行语句的次数。 当我们面前有多...
  • 即算法的时间复杂度和空间复杂度统称为算法的时间复杂度。   时间复杂度 计算一下下面程序的循环语句总共会执行多少次? void Test(int n) { int iConut = 0; for (int i = 0; i &lt; n; ++i) { ...
  • 算法的时间复杂度和空间复杂度-总结

    万次阅读 多人点赞 2013-09-20 16:01:26
    算法的时间复杂度和空间复杂度 1、时间复杂度 (1)时间频度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的...
  • 算法 时间复杂度 空间复杂度 经典算法 时间复杂度 空间复杂度 经典算法 时间复杂度 空间复杂度 经典
  • 简析时间复杂度和空间复杂度

    万次阅读 多人点赞 2019-06-25 16:24:17
    时间复杂度和空间复杂度是用来评价算法效率高低的2个标准,身为开发者肯定会经常会听到这2个概念,但它们分别是什么意思呢? 其实这两个概念从字面意思上也能看出一二: 时间复杂度:就是说执行算法需要消耗的时间...
  • 使用空间(内存)就是空间复杂度 二 . 时间复杂度 我们知道, CPU每秒运行的指令数是恒定的, 衡量算法快慢的标准就是算法运行的基本指令个数, 运行指令个数f(n)和数据规模n有关 现在来了解一下大O渐进法, 这个方法...
  • **时间复杂度(维基百科)** !... 对{123,423,412,023}进行基数排序,B是10,蓝色部分N是10^3 ...对{as,qe,sd,fa,as,ws}进行基数排序,B是26,蓝色部分N是26^2 ...k就是:位数(也可以...**我觉得空间复杂度是O(n+r)**
  • 1.空间复杂度 计算方法 2.时间复杂度 计算方法 非递归 递归情况递归总次数*每次递归次数 1.空间复杂度 空间复杂度是指 执行这个算法所需要的内存空间。 空间复杂度是函数中创建对象的个数关于问题规模...
  • 一、空间复杂度定义 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。 一个算法在计算机存储器上所占用的存储空间,包括程序代码所占用的空间,输入数据所占用的空间和辅助变量所...
  • 空间复杂度不太了解,今天在做算法题时候突然想到这个问题。 空间复杂度是仅仅算方法块内部的局部变量,还是要把for循环的i以及其他的在其内部定义的局部变量也算进去?(这个i算不算局部变量?如果算,是算for里...
  • 已知长度为n的线性表A采用顺序存储结构,请写一个时间复杂度为O(n)、空间复杂度为O(1)的算法,该算法可删除线性表中所有值为item的数据元素。

空空如也

1 2 3 4 5 ... 20
收藏数 42,785
精华内容 17,114
关键字:

空间复杂度