空间复杂度 订阅
空间复杂度(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较大时,将占用较多的存储单元,例如快速排序和归并排序算法就属于这种情况。
收起全文
精华内容
下载资源
问答
  • 空间复杂度

    2018-06-15 23:11:30
    空间复杂度

    空间复杂度

    前面刚讲了时间复杂度,有兴趣的去看看什么是时间复杂度?

    名词解释:空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了,因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

    度量方法

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

    分析方法

    分析一个算法所占用的存储空间要从各方面综合考虑。如对于递归算法来说,一般都比较简短,算法本身所占用的存储空间较少,但运行时需要一个附加堆栈,从而占用较多的临时工作单元;若写成非递归算法,一般可能比较长,算法本身占用的存储空间较多,但运行时将可能需要较少的存储单元。
    一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小,它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。若一个算法为 [2] 递归算法,其空间复杂度为递归所使用的堆栈空间的大小,它等于一次调用所分配的临时存储空间的大小乘以被调用的次数(即为递归调用的次数加1,这个1表示开始进行的一次非递归调用)。算法的空间复杂度一般也以数量级的形式给出。如当一个算法的空间复杂度为一个常量,即不随被处理数据量n的大小而改变时,可表示为O(1);当一个算法的空间复杂度与以2为底的n的对数成正比时,可表示为O(log2n);当一个算法的空间复杂度与n成线性比例关系时,可表示为O(n).若形参为数组,则只需要为它分配一个存储由实参传送来的一个地址指针的空间,即一个机器字长空间;若形参为引用方式,则也只需要为其分配存储一个地址的空间,用它来存储对应实参变量的地址,以便由系统自动引用实参变量。
    故一个算的空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。所以它强调的是使用的辅助空间的的大小,而不是指所有的数据所占用的空间。
    以斐波那契算法为例子:

    long long* fib(long long n)  
    {  
        assert(n>=0);  
        long long* ptr=new long long[n+1];  
        ptr[0]=0;  
        ptr[1]=1;  
        for(int i=2;i<=n;++i)  
        {  
            ptr[i]=ptr[i-1]+ptr[i-2];  
        }  
        return ptr;  
    }  
    /*对于这种算法,函数真正执行次数为n-1,所以忽略常数后,时间复杂度为O(n);
    因为开辟了n+1个空间,有n+1个辅助空间,所以空间复杂度为O(n).*/
    long long fib(long long n)  
    {  
        assert(n>=0);  
        long long first=0;  
        long long second=1;  
        long long ret=0;  
            for(int i=2;i<=n;i++)  
        {  
            ret=first+second;  
            first=second;  
            second=ret;  
        }  
        return ret;  
    }  
    /*这是非递归的另一种算法,函数真正执行次数依然为n-1,所以忽略常数后,时间复杂度还是O(n);
    由于采用变量交换的方式,所以在这里辅助空间个数为一个常数,空间复杂度为O(1).*/
    
    
    //递归写法
    #include<assert.h>  
    #include<iostream>  
    using namespace std;  
    long long fib(long long n)  
    {  
        assert(n>=0);  
        return (n<2)?(n):(fib(n-1)+fib(n-2));  
    }  
    /*递归算法的时间复杂度计算方法是:递归总次数*每次递归次数;
    递归算法的时间复杂度计算方法是:递归深度*每次递归所需的辅助空间个数.
    可以得出斐波那契递归算法时间复杂度:O(2^N),空间复杂度为:O(N)*/
    
    int main()  
    {  
        long long value=fib(15);  
        cout<< value <<endl;  
        system("pause");  
        return 0;  
    }  

    时间复杂度与空间复杂度的联系

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

    展开全文
  • 时间复杂度和空间复杂度的简单讲解

    万次阅读 多人点赞 2018-01-07 12:55:26
    文章最后,举例使用二分查找和斐波那契的递归和迭代方法,分别说明时间和空间复杂度。 时间复杂度: 首先要说的是,时间复杂度的计算并不是计算程序具体运行的时间,而是算法执行语句的次数。 当我们面前有多...

    一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

    把今年很流行,淡淡的基佬紫送给各位看官,原谅绿就算了,怕被打死。

    文章最后,举例使用二分查找和斐波那契的递归和迭代方法,分别说明时间和空间复杂度。

    时间复杂度:
    首先要说的是,时间复杂度的计算并不是计算程序具体运行的时间,而是算法执行语句的次数。
    当我们面前有多个算法时,我们可以通过计算时间复杂度,判断出哪一个算法在具体执行时花费时间最多和最少。

    常见的时间复杂度有:
    常数阶O(1),
    对数阶O(log2 n),
    线性阶O(n),
    线性对数阶O(n log2 n),
    平方阶O(n^2),
    立方阶O(n^3)
    k次方阶O(n^K),
    指数阶O(2^n)。
    随着n的不断增大,时间复杂度不断增大,算法花费时间越多。

    计算方法
    ①选取相对增长最高的项
    ②最高项系数是都化为1
    ③若是常数的话用O(1)表示
    如f(n)=2*n3+2n+100则O(n)=n3。

    通常我们计算时间复杂度都是计算最坏情况
    时间复杂度的计算:
    (1)如果算法的执行时间不随着问题规模n的增加而增长,即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

            int x=1;
    	while (x <10)
    	{
    		x++;
    	}
    

    该算法执行次数是10,是一个常数,用时间复杂度表示是O(1)。

    (2)当有若干个循环语句时,算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。

    	for (i = 0; i < n; i++)
    	{
    		for (j = 0; j < n; j++)
    		{
    			;
    		}
    	}
    

    该算法for循环,最外层循环每执行一次,内层循环都要执行n次,执行次数是根据n所决定的,时间复杂度是O(n^2)。

    (3)循环不仅与n有关,还与执行循环所满足的判断条件有关。

    int i=0;
    while (i < n && arr[i]!=1)
    	{
    		i++;
    	}
    

    在此循环,如果arr[i]不等于1的话,时间复杂度是O(n)。如果arr[i]等于1的话,则循环执行一次判断跳出,时间复杂度是O(1)。

    空间复杂度
    空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。
    计算方法:
    ①忽略常数,用O(1)表示
    ②递归算法的空间复杂度=递归深度N*每次递归所要的辅助空间
    ③对于单线程来说,递归有运行时堆栈,求的是递归最深的那一次压栈所耗费的空间的个数,因为递归最深的那一次所耗费的空间足以容纳它所有递归过程。

    如:

    int a;
    int b;
    int c;
    printf("%d %d %d \n",a,b,c);
    

    它的空间复杂度O(n)=O(1);

    int fun(int n,)
    {
    int k=10;
    if(n==k)
    return n;
    else
    return fun(++n);
    }
    

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

    #举例说明

    1:实现二分查找算法的递归及非递归。(分析时间复杂度及空间复杂度)

    迭代算法

    #define _CRT_SECURE_NO_WARNINGS
    
    #include<stdio.h>
    #include<string.h>
    #include<assert.h>
    
    int BinarySearch(int arr[], int len, int num)
    {
    	assert(arr);
    
    	int left = 0;
    	int right = len - 1;
    	int mid;
    
    	while (left <= right)
    	{
    		mid = left + (right - left) / 2;
    
    		if (num > arr[mid])
    		{
    			left = mid + 1;
    		}
    		else if (num < arr[mid])
    		{
    			right = mid - 1;
    		}
    		else
    		{
    			return mid;
    		}
    	}
    
    	return -1;
    }
    
    
    
    int main()
    {
    	int arr[] = { 1,2,3,4,5,6,7,8,9 };
    	int length = sizeof(arr) / sizeof(arr[0]);
    	int aim = 9;
    	int result;
    
    	result = BinarySearch(arr, length, aim);
    
    	if (result == -1)
    	{
    		printf("Can't find %d\n", aim);
    	}
    	else
    	{
    		printf("%d at %d postion\n", aim,result + 1);
    	}
    	
    
    	return 0;
    }
    

    二分查找时,每次都在原有查找内容进行二分,所以时间复杂度为O(log2 n)
    因为变量值创建一次,所以空间复杂度为O(1)

    递归算法

    int BinarySearchRecursion(int arr[5], int lef, int rig,int aim)
    {
    	int mid = lef + (rig - lef) / 2;
    
    	
    	if (lef <= rig)
    	{
    		if (aim < arr[mid])
    		{
    			rig = mid - 1;
    			BinarySearchRecursion(arr, lef, rig, aim);
    		}
    		else if (arr[mid] < aim)
    		{
    			lef = mid + 1;
    			BinarySearchRecursion(arr, lef, rig, aim);
    		} 
    		else if (aim == arr[mid])
    		{
    			return mid;
    		}
    		
    	}
    	else
    		return -1;
    	
    }
    
    
    int main()
    {
    	int arr[] = { 1,2,3,5,6, };
    	int sz = sizeof(arr)/sizeof(arr[0]);
    	int result;
    
    	result = BinarySearchRecursion(arr, 0, sz - 1, 4);
    
    	if (-1 == result)
    	{
    		printf("Can't find it.\n");
    	}
    	else
    		printf("Aim at %d location\n", result+1);
    }
    

    时间复杂度为O(log2 n)
    每进行一次递归都会创建变量,所以空间复杂度为O(log2 n)

    2:实现斐波那契数列的递归及非递归。(分析时间复杂度及空间复杂度)

    迭代算法

    int FeiBoNaCciInteration(int a,int b,int num)
    {
    	int c;
    
    	if (num <= 0)
    		return -1;
    	else if (num == 1)
    		return a;
    	else if (num == 2)
    		return b;
    	else
    	{
    		while (num - 2)
    		{
    			c = a + b;
    			a = b;
    			b = c;
    			num--;
    		}
    		return c;
    	}
    	
    }
    
    int main()
    {
    	int n;
    	int result;
    
    	printf("Input n\n");
    	scanf("%d", &n);
    
    	result = FeiBoNaCciInteration(2, 3, n);//可自定义输入第一个数和第二个数
    	if (result == -1)
    	{
    		printf("Input Error!\n");
    	}
    	else
    	{
    		printf("n is %d\n", result);
    	}
    
    	return 0;
    }
    

    时间复杂度O(n)
    空间复杂度为O(1)

    递归算法

    int FeiBoNaCciRecursion(int num)
    {
    	if (num < 0)
    		return -1;
    	if (num <= 2 && num > 0)
    		return 1;
    	else
    		return FeiBoNaCciRecursion(num - 1) + FeiBoNaCciRecursion(num - 2);
    	
    }
    
    int main()
    {
    	int n;
    	int result;
    
    	printf("Input n\n");
    	scanf("%d", &n);
    
    	result = FeiBoNaCciRecursion(n);
    
    	if (result == -1)
    		printf("Input Error!\n");
    	else
    		printf("Result is %d\n", result);
    
    	return 0;
    }
    

    时间复杂度为O(2^n)
    空间复杂度为O(n)

    欢迎在评论区留言提问,谢谢!

    另外,如果觉得文章对你有用,下边点个打赏吧!

    你们的支持,是我坚持的动力。

    展开全文
  • 一、空间复杂度定义 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。 一个算法在计算机存储器上所占用的存储空间,包括程序代码所占用的空间,输入数据所占用的空间和辅助变量所...

    一、空间复杂度定义

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

    二、影响空间复杂度的因素

    在这里插入图片描述
    注意:
    一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小,它包括为参数表中形参变 量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。若一个算法为递归算法,其空间复杂度为递归所使用的堆栈空间的大小。它等于一次调用所分配的临时存储空间的大小乘以被调用的次数(即为递归调用的次数加1,这个1表示开始进行的一次非递归调用)
    递归的空间复杂度: 每次递归所开空间*深度。

    算法在运行过程中临时占用的存储空间讲解:
    1、有的算法只需要占用少量的临时工作单元,而且不随问题规模的大小而改变,我们称这种算法是“就地”进行的,是节省存储的算法,下面会介绍。

    2、有的算法需要占用的临时工作单元数与解决问题的规模n有关,它随着n的增大而增大,当n较大时,将占用较多的存储单元,例如快速排序和归并排序算法就属于这种情况。

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

    四、例子

    1、空间算法的常数阶
    在这里插入图片描述
    如上图,这里有三个局部变量分配了存储空间,所以f(n) = 1 + 1 + 1 = 3,根据上面的法则该函数不受n的影响且为常数项,所以空间复杂度记作O(1)。这种与问题的大小无关(n的多少),执行时间恒定的算法,我们称之为具有O(1)的空间复杂度,又叫常数阶。

    2.空间算法的线性阶(递归算法)
    在这里插入图片描述
    如上图,这是一个递归算法(计算从n + (n-1) + (n-2) + … + 2 + 1的和)
    每当执行一次该函数就会为tmp分配一个临时存储空间,所以f(n) = 1*(n-1+1) = n,函数是受n影响的所以空间复杂度记为O(n)。

    3、二分查找分析

    在这里插入图片描述

    方法一(迭代法):

    /// <summary>
    /// 二分查找
    /// </summary>
    /// <param name="arr">查找数组</param>
    /// <param name="len">数组长度</param>
    /// <param name="num">查找项</param>
    /// <returns></returns>
    int BinarySearch(int[] arr,int len,int num)
    {
        int left = 0;
        int right = len - 1;
        int mid;
        while (left <= right)
        {
            mid = (left + right) / 2;
            if (arr[mid] > num)
                right = mid - 1;
            else if (arr[mid] < num)
                left = mid + 1;
            else
                return mid;
        }
        return -1;
    }
    

    时间复杂度:
    left、right、mid运算次数
    f(n1) = 1 + 1 + 1 = 3
    我们将While循环中的运算作为一个整体看待,每次都是折半运算次数
    f(n2) = log2^n
    总运行次数
    f(all) = f(n1)+f(n2) = 3 + log2 ^ n
    时间复杂度记为:O(log2^n)


    空间复杂度:
    算法中left、right、mid只创建的次数
    s(n) = 1 + 1 + 1 = 3
    空间复杂度记为:O(1)


    方法二(递归法):

     /// <summary>
    /// 二分查找(递归法)
    /// </summary>
    /// <param name="arr"></param>
    /// <param name="left"></param>
    /// <param name="right"></param>
    /// <param name="num"></param>
    /// <returns></returns>
    int BinarySearchRecursion(int[] arr,int left,int right,int num)
    {
        int mid = (left + right) / 2;
        if (left <= right)
        {
            if (arr[mid] > num) {
                right = mid - 1;
                return BinarySearchRecursion(arr,left,right,num);
            }
            else if (arr[mid] < num)
            {
                left = mid + 1;
                return BinarySearchRecursion(arr,left,right,num);
            }
            else
                return mid;
        }
        else
        {
            return -1;
        }
    }
    

    时间复杂度:
    运行次数 f(n) = log2 ^ n
    时间复杂度记为:O(log2^n)


    空间复杂度:
    因为整个算法中mid只创建的次数
    s(n) = log2 ^ n
    空间复杂度记为:O(log2 ^ n)


    4、斐波那契数列

    斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……
    这个数列从第3项开始,每一项都等于前两项之和。

    如果设F(n)为该数列的第n项(n∈N*),那么这句话可以写成如下形式::F(n)=F(n-1)+F(n-2)

    显然这是一个线性的递推数列。
    通项公式 :
    在这里插入图片描述
    上面就是斐波那契数列的递推公式,这样一个完全是自然数的数列,通项公式却是用无理数来表达的。而且当n趋向于无穷大时,前一项与后一项的比值越来越逼近黄金分割0.618
    在这里插入图片描述
    递推是公式是求解斐波那契数列的一个方法,我们当然也可以用计算机编写程序来求解。

    方法一(迭代法):

    /// <summary>
    /// 斐波那契(迭代法)
    /// </summary>
    /// <param name="n"></param>
    /// <returns></returns>
    int Fibonacci(int n)
    {
        if (n <= 0)
            return -1;
        if (n == 1 || n == 2)
            return 1;
        else
        {
            int num = 0;
            int a = 1;
            int b = 1;
            while (n - 2 > 0)
            {
                num = a + b;
                a = b;
                b = num;
                n--;
            }
            return num;
        }
    
    }
    

    时间复杂度:
    while以外的算法语句都忽略不计(不随n的变化而变化)
    while算法语句所有语句
    f(n) = 4 *(n - 2) = 4n - 8
    时间复杂度记为:O(n)


    空间复杂度:
    算法中num、a、b只创建1次
    s(n) = 1 + 1 + 1 = 3
    空间复杂度记为:O(1)


    方法二(递归法):

    /// <summary>
    /// 斐波那契(递归法)
    /// </summary>
    /// <param name="n"></param>
    /// <returns></returns>
    int FibonacciRecursion(int n)
    {
        if (n <= 0)
            return -1;
        if (n == 1 || n == 2)
            return 1;
        return FibonacciRecursion(n - 1) + FibonacciRecursion(n - 2);
    }
    

    时间复杂度:
    递归调用的形参有两个n - 1 和 n - 2
    时间复杂度记为:O(2^n)


    空间复杂度:
    递归的空间复杂度 =(n + 1)* 调用的深度
    空间复杂度记为:O(n)(这里可以简单的根据二叉树的层来进行计算)


    展开全文
  • 1.空间复杂度 计算方法 2.时间复杂度 计算方法 非递归 递归情况递归总次数*每次递归次数 1.空间复杂度 空间复杂度是指 执行这个算法所需要的内存空间。 空间复杂度是函数中创建对象的个数关于问题规模...

    1.空间复杂度

    • 空间复杂度是指 执行这个算法所需要的内存空间。
    • 空间复杂度是函数中创建对象的个数关于问题规模函数表达式,一般情况下用O渐进表示法表示

    计算方法

    1.忽略常数,用O(1)表示
    2.递归算法的空间复杂度=递归深度*每次递归所要的辅助空间
    3.对于单线程来说,递归有运行时堆栈,求的是递归最深的那一次压栈所耗费的空间的个数,因为递归最深的那一次所耗费空间足以容纳它所有递归过程。递归是要返回上一层的,所以它所需要的空间不是一直累加起来的。

    2.时间复杂度

    • 时间复杂度是指 执行这个算法所需要的计算工作量。

    计算方法

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

    非递归

    void Test(int n)
    {
        int iCount = 0;
        for (int iIdx = 0; iIdx < 10; ++iIdx)
        {
            iCount++;
        }
    }
    
    
    //执行总次数:f(n)=10 + 1
    //则O(n)=O(1)

    递归情况递归总次数*每次递归次数

    int Jie_Cheng(int n)
    {
        if (n < 2)
            return 1;
        else
            int i = n;
            int tmp = Jie_Cheng(n - 1);
            return n * tmp;
    }
    //每次递归次数:2
    //递归总次数:n
    //2*n   所以O(n)=O(n)
    展开全文
  • 简析时间复杂度和空间复杂度

    万次阅读 多人点赞 2019-06-25 16:24:17
    时间复杂度和空间复杂度是用来评价算法效率高低的2个标准,身为开发者肯定会经常会听到这2个概念,但它们分别是什么意思呢? 其实这两个概念从字面意思上也能看出一二: 时间复杂度:就是说执行算法需要消耗的时间...
  • 算法的时间复杂度和空间复杂度-总结

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

    万次阅读 多人点赞 2017-05-15 20:38:47
    算法复杂度分为时间复杂度和空间复杂度。 其作用: 时间复杂度是指执行算法所需要的计算工作量; 而空间复杂度是指执行这个算法所需要的内存空间。 (算法的复杂性体现在运行该算法时的计算机所需资源的多少上,...
  • 使用空间(内存)就是空间复杂度 二 . 时间复杂度 我们知道, CPU每秒运行的指令数是恒定的, 衡量算法快慢的标准就是算法运行的基本指令个数, 运行指令个数f(n)和数据规模n有关 现在来了解一下大O渐进法, 这个方法...
  • 前言: 时间复杂度是执行算法的时间成本,空间复杂度是执行算法的空间成本。 人们之所以花大力气去评估算法的时间复杂度和空间复杂度,其根本原因是计算机的运行速度和空间都是有限的。 在运行一段程序时,不仅要...
  • 排序算法时间复杂度、空间复杂度、稳定性比较

    万次阅读 多人点赞 2017-07-30 21:33:22
    空间复杂度 是否稳定 冒泡排序 :————-: :—–: :—–: :—–: 选择排序 :————-: :—–: :—–: :—–: 直接插入排序 :————-: :—–: :—–: :—–: 归并排序 :————-: :—–: :

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 46,051
精华内容 18,420
关键字:

空间复杂度