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

    leetcode 26 – 删除排序数组中的重复项
    给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

    不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

    if(nums.length < 1) return 0;
        	  int i = 0;
        	  for(int j=1; j<nums.length; j++) {
        		  if(!(nums[i] == nums[j])) {
        			  nums[i+1] = nums[j];
        			  i++;
        		  }
        	  }
     return i+1;
    

    复杂度也叫渐进复杂度,包括时间复杂度和空间复杂度,用来分析算法执行效率与数据规模之间的增长关系,可以粗略地表示,越高阶复杂度的算法,执行效率越低。

    空间复杂度: 全称是 渐进空间复杂度,表示算法的存储空间与数据规模之间的增长关系。
    时间复杂度: 全称是 渐进时间复杂度,表示算法的执行时间与数据规模之间的增长关系。

    1、空间复杂度

    一个程序的空间复杂度是指运行完一个程序所需内存的大小。
    利用程序的空间复杂度,可以对程序的运行所需的内存有个预先估计。

    程序执行时所需存储空间包括以下两部分:

    • 固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间(即代码空间)、数据空间(常量、简单变量)等所占的空间。这部分属于静态空间。

    • 可变空间。这部分空间主要包括动态分配的空间,以及递归栈所需的空间等。这部分的空间大小与算法有关。

    我们在写代码时,完全可以用空间来换取时间,比如字典树、哈希等都是这个原理。HashMap.get()、put()都是O(1)的时间复杂度。

    空间复杂度为O(1):有的算法只需要占用少量的临时工作单元,而且不随问题规模的大小而改变,我们称这种算法是“就地”执行的,是节省存储的算法,空间复杂度为O(1)。

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

    常见的空间复杂度就是O(1)、O(n)、O(n^2),像是O(logn)、O(nlogn)对数阶的复杂度平时都用不到,而且空间复杂度分析比时间复杂度分析要简单很多。

    (1)空间复杂度为:O(1)

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

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

    (2)空间复杂度:O(n)

    void print(int n) {
      int i = 0;
      int[] a = new int[n];
      for (i; i <n; ++i) {
        a[i] = i * i;
      }
    }
    

    第三行new了一个数组,这个数组占用的大小为n,虽然后面有循环,但是没有再分配新的空间,因此空间复杂度S(n) = O(n)。

    2、时间复杂度

    (1)T(n) = O(2n+2) (看不懂没关系,后面有解释) 时间复杂度:O(n)

    int cal(int n) {
       int sum = 0;
       int i = 1;
       for (; i <= n; ++i) {
         sum = sum + i;
       }
       return sum;
     }
    
    

    假设每行代码的执行时间都是一样的,为unit_time单位时间。

    第 2、3 行代码分别需要== 1 个 unit_time== 的执行时间,第 4、5 行都运行了 n 遍,所以需要 2n*unit_time 的执行时间,所以这段代码总的执行时间就是== (2n+2)*unit_time==。可以看出来,所有代码的执行时间 T(n) 与每行代码的执行次数成正比。

    (2)T(n) = O(2n2+ 2n + 3) 时间复杂度:O(n^2)

    int cal(int n) {
       int sum = 0;
       int i = 1;
       int j = 1;
       for (; i <= n; ++i) {
         j = 1;
         for (; j <= n; ++j) {
           sum = sum +  i * j;
         }
       }
     }
    
    

    第 2、3、4 行代码,每行都需要 1 个 unit_time 的执行时间,第 5、6 行代码循环执行了 n 遍,需要 2n * unit_time 的执行时间,第 7、8 行代码循环执行了 n2遍,所以需要 2n2 * unit_time 的执行时间。所以,整段代码总的执行时间 T(n) = (2n2+ 2n + 3)*unit_time。

    规律:所有代码的执行时间T(n)与每行代码的执行次数成正比
    把规律总结成一个公式: T(n) = O(f(n))
    其中,f(n)表示每行代码执行的次数总和,因为是一个公式,所以用f(n)来表示; O表示代码的执行时间T(n)与f(n)表达式成正比。

    上面是大O时间复杂度的由来和表示方法,但是分析代码的时间复杂度,一般有三种方式:(1)只关注循环执行次数最多的一段代码;(2)总的时间复杂度就等于量级最大的那段代码的时间复杂度;(3)嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。

    几种常见的时间复杂度实例
    1、常量阶 O(1)O(1)O(1)
    2、对数阶 O(logn)O(logn)O(logn)
    3、线性阶 O(n)O(n)O(n)
    4、线性对数阶 O(nlogn)O(nlogn)O(nlogn)
    5、平方阶 O(n2)、立方阶 O(n3)……k 次方阶 O(nk)
    6、指数阶 O(2n)
    7、阶乘阶 O(n!)

    (1)O(1)

    int a = 1;
    int b = 2;
    int c = 3;
    

    一般情况下,只要算法中不存在循环语句、递归语句,即使有成千上万行的代码,其时间复杂度也是Ο(1)。
    (2)O(logn)、O(nlogn)

     i=1;
     while (i <= n)  {
       i = i * 2;
     }
    

    执行次数为log2n,所以,这段代码的时间复杂度为O(log2n)

     i=1;
     while (i <= n)  {
       i = i * 3;
     }
    

    执行次数为log3n,所以,这段代码的时间复杂度为O(log3n)
    实际上,不管是以2为底、以3为底还是以10为底,我们可以把所有对数阶的时间复杂度都记为O(logn),忽略对数的底。

    for(m = 1; m < n; m++) {
        i = 1;
        while(i < n) {
            i = i * 2;
        }
    }
    

    上述的时间复杂度为O(nlogn)

    (3)O(m+n)、O(m*n)
    代码的复杂度由两个数据的规模来决定

    int cal(int m, int n) {
      int sum_1 = 0;
      int i = 1;
      for (; i < m; ++i) {
        sum_1 = sum_1 + i;
      }
     
      int sum_2 = 0;
      int j = 1;
      for (; j < n; ++j) {
        sum_2 = sum_2 + j;
      }
     
      return sum_1 + sum_2;
    }
    

    代码中,m和n表示两个数据规模,我们无法事先评估m和n谁的量级大,所以上面代码的时间复杂度就是O(m+n)。

    (4)O(n)

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

    (5)O(n^2)

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

    二分查找的时间复杂度:logn
    https://www.cnblogs.com/yellowgg/p/11272908.html

    参考:
    https://juejin.cn/post/6844904167824162823
    https://juejin.cn/post/6844904087876534280

    更多相关内容
  • 算法复杂度分为时间复杂度和空间复杂度。 其作用: 时间复杂度是指执行算法所需要的计算工作量; 而空间复杂度是指执行这个算法所需要的内存空间。 (算法的复杂性体现在运行该算法时的计算机所需资源的多少上,...
  • 今天有同事在检查代码的时候,由于函数写的性能不是很好,被打回去重构了,细思极恐,今天和大家分享一篇用js讲解的时间复杂度和空间复杂度的博客 2. 复杂度的表示方式 之前有看过的,你可能会看到这么一串东西 T...
  • 算法时间复杂度和空间复杂度 1.算法效率 算法效率分析分为两种:第一种是时间效率,第二种是空间效率。时间效率被称为时间复杂度,而空间效率被称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度,而空间...

    算法时间复杂度和空间复杂度

    1.算法效率

    算法效率分析分为两种:第一种是时间效率,第二种是空间效率。时间效率被称为时间复杂度,而空间效率被称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度,而空间复杂度主要衡量一个算法所需要的额外空间,在计算机发展的早期,计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展,计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

    2.时间复杂度

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

    3.空间复杂度

    空间复杂度是对一个算法在运行过程中临时占用存储空间大小量度 。空间复杂度不是程序占用了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似,也使用大O渐进表示法。

    4.大O渐进表示法

    • 大O符号(Big O notation):是用于描述函数渐进行为的数学符号。推导大O阶方法:
    • 1、用常数1取代运行时间中的所有加法常数。
    • 2、在修改后的运行次数函数中,只保留最高阶项。
    • 3、如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。

    另外有些算法的时间复杂度存在最好、平均和最坏情况:

    • 最坏情况:任意输入规模的最大运行次数(上界) 平均情况:任意输入规模的期望运行次数
    • 最好情况:任意输入规模的最小运行次数(下界) 例如:在一个长度为N数组中搜索一个数据x 最好情况:1次找到 最坏情况:N次找到
    • 平均情况:N/2次找到 在实际中一般情况关注的是算法的最坏运行情况,所以数组中搜索数据时间复杂度为O(N)

    5.常见时间复杂度

    计算一下这个算法的时间复杂度

    // 请计算一下Func1基本操作执行了多少次?void Func1(int N) { int count = 0;//两层循环嵌套外循环执行n次,内循环执行n次,整体计算就是N*N的执行次数for (int i = 0; i < N ; ++ i) { 	 for (int j = 0; j < N ; ++ j)	 { 		 ++count;	 }}//2 * N的执行次数for (int k = 0; k < 2 * N ; ++ k){ 	 ++count;}//常数项10int M = 10;while (M--) {  	++count;  } printf("%d\n", count);}
    

    精确的时间复杂度是N ^ 2 + 2 * N + 10
    大O的渐进表示法时间复杂度是O(N ^ 2)
    分析:
    1、两层循环嵌套外循环执行n次,内循环执行n次,整体计算就是N*N 的执行次数
    2、2 * N的执行次数
    3、常数项10
    根据前面的大o渐进表示法规则,所以最后只保留那项对执行次数影响最大的那一项,时间复杂度就是O(N ^ 2)
    img

    计算一下这个算法的时间复杂度

    // 计算Func2的时间复杂度?void Func2(int N) { 	int count = 0;	for (int k = 0; k < 2 * N ; ++ k) 	{ 		++count; 	}		int M = 10;	while (M--) 	{ 	++count; }	printf("%d\n", count);}
    

    精确的算法执行次数是2 * n + 10
    采用大O渐进表示法规则后时间复杂度是O(N)
    如果最高阶项存在且不是1,则去除与这个项目相乘的常数,那保留的就会是O(N)

    计算一下这个算法的时间复杂度

    // 计算Func3的时间复杂度?void Func3(int N, int M){ 	//执行M次	int count = 0;	for (int k = 0; k < M; ++ k) 	{ 		++count; 	}	//执行N次	for (int k = 0; k < N ; ++ k) 	{ 		++count; 	}	printf("%d\n", count);}
    

    时间复杂度:O(M + N)
    假设:
    M远大于N --> O(M)
    N远大于M --> O(N)
    M和N一样大 --> O(M) / O(N)
    还是取影响最大的那一项,如果并没有说明M和N的大小关系,那么时间复杂度就是O(M + N)

    计算一下这个算法的时间复杂度

    // 计算Func4的时间复杂度?void Func4(int N) { 	int count = 0;	for (int k = 0; k < 100; ++ k) 	{ 		++count; 	}	printf("%d\n", count);}
    

    时间复杂度:O(1)
    循环执行的次数是常数次,常数取1

    计算一下这个算法的时间复杂度

    // 计算strchr的时间复杂度?const char * strchr ( const char * str, int character ){ 	while(*str)	{ 		if(*str == character)			return *str;		else			str++;	}}
    

    时间复杂度:O(N)
    最坏情况:遍历到最后才找到或者字符串中压根就没有,O(N)
    平均情况:O(N / 2) , 忽略系数项是O(N)
    最好情况:一次就找到了,O(1)

    计算一下这个算法的时间复杂度

    // 计算BubbleSort的时间复杂度?void BubbleSort(int* a, int n) { 	assert(a);	for (size_t end = n; end > 0; --end)	 { 		int exchange = 0;		for (size_t i = 1; i < end; ++i)		{ 			if (a[i-1] > a[i])			{ 				Swap(&a[i-1], &a[i]);				exchange = 1;			}		}		if (exchange == 0)		break; 	} }
    

    精确的时间复杂度:O(N * (N-1) / 2)
    冒泡排序的思想是:假设给你N个元素,让你排升序,对N个元素排升序,只需要执行N - 1趟,两两相比较,每趟交换都会将最大的那个元素换到最后面去,这样子一来最大的数就都集中在后面,不就相当于每排序一趟后就少比较一个元素嘛,因为后面已经是最大的了不需要再交换。
    通过公式展开后采用大O渐进表示法规则后,时间复杂度:O(N ^ 2)

    计算一下这个算法的时间复杂度

    // 计算BinarySearch的时间复杂度?int BinarySearch(int* a, int n, int x){ 	assert(a);	int begin = 0;	int end = n-1; .		while (begin < end) 	{ 		int mid = begin + ((end-begin)>>1);		if (a[mid] < x)			begin = mid+1;		else if (a[mid] > x)			end = mid;		else			return mid; 	}	return -1; }
    

    先来理解二分查找的思想:
    二分查找是通过下标来搜索对应的元素值,前提是这个数组是有序的,通过确定中间位置划分左右区间,如果val小于mid那么目标值排除了出现在右边的情况,继续再左边区间查找,确定中间下标,通过中间下标划分左右区间,直到找到,否则一直重复规则直到循环结束,理解了二分查找的思想我们能想到的几种情况
    img

    最坏情况:O(log N)

    每次确定中间下标,划分左右区间的时候都会除以2,那么
    N / 2
    N / 4
    N / 8
    .
    .
    .
    1 //等于1的时候找到了
    当找到了,要想知道它的执行次数的时候,通过它的展开就能知道
    1 * 2 * 2 * 2 * 2 = N
    2 ^ x = N
    x = log N (以2为底,N的对数)

    平均情况:不考虑
    最好情况:O(1)

    计算一下这个算法的时间复杂度

    // 计算阶乘递归Factorial的时间复杂度?long long Factorial(size_t N) { 	return N < 2 ? N : Factorial(N-1)*N; }
    

    时间复杂度:O(N)
    这个算法,递归的开始条件是当N >= 2,它的结束条件是N < 2,当条件成立的时候会一直递归下去,直达条件为假递归终止才会将结果返回,递归的深度决定的是算法的时间复杂度,
    N - 1
    N - 2
    N - 3
    .
    .
    2
    1 //递归结束,递归的层数是N

    计算一下这个算法的时间复杂度

    // 计算斐波那契递归Fibonacci的时间复杂度?long long Fibonacci(size_t N) { 	return N < 2 ? N : Fibonacci(N-1)+Fibonacci(N-2);}
    

    时间复杂度:O(2 ^ N)
    经典的递归分治算法,读者可以将它看成一个完全二叉树,在它递归层层展开的时候开辟的栈帧看作是一个结点,每创建一个结点都是一次函数调用,那么在脑海中想象出来的场景是这样的,可以看到它的调用次数是 Fib(N) = 2 ^0 + 2 ^1 + 2 ^ 2 + … + 2 ^(n -1) - x
    时间复杂度:O(2 ^ N)
    img

    计算一下这个算法的空间复杂度

    // 计算BubbleSort的空间复杂度?void BubbleSort(int* a, int n) {  assert(a); for (size_t end = n; end > 0; --end) {  	int exchange = 0; 	for (size_t i = 1; i < end; ++i)	 { 	 	if (a[i-1] > a[i]) 		{  			Swap(&a[i-1], &a[i]); 			exchange = 1; 		} 	} 	 	if (exchange == 0) 		break; }}
    

    空间复杂度:O(1),常数个额外的变量

    计算一下这个算法的空间复杂度

    // 计算Fibonacci的空间复杂度?long long* Fibonacci(size_t n) {  if(n==0) return NULL;  long long * fibArray =(long long *)malloc((n+1) * sizeof(long long)); fibArray[0] = 0; fibArray[1] = 1;for (int i = 2; i <= n ; ++i) {  fibArray[i ] = fibArray[ i - 1] + fibArray [i - 2]; } return fibArray ;}
    

    空间复杂度O(N),malloc了N+1个long long大小的空间

    计算一下这个算法的空间复杂度

    long long Factorial(size_t N) { 	 return N < 2 ? N : Factorial(N-1)*N; }
    

    空间复杂度O(N),之前说时间复杂度的时候讲这个例子是每调用一次这个函数就会开辟一次栈帧,调用了N次

    long long Fib(size_t N){ 	if(N < 3)		return	else		return Fib(N - 1) + Fib(N - 2); }
    

    空间复杂度是O(N)
    再之前讲时间复杂度的时候用这个例子,说的是将它看成一个完全二叉树,在它递归层层展开的时候开辟的栈帧看作是一个结点,每创建一个结点都是一次函数调用,当然计算时间复杂度符合这个特性,因为时间是不可复用的,而如果以空间复杂度的角度来计算的话,结果却并不是这样子,因为空间是可以复用的,每次递归调用,当Fib(N-1)递归完了,就会将内存归还给操作系统,进而才递归Fib(N - 2),所以空间复杂度是O(N)

    常见复杂度对比

    img

    img

    oj练习

    17.04. 消失的数字
    链接: [link](javascript:void(0)).

    题目描述:
    数组nums包含从0到n的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗?

    • 思路一:快速排序 时间复杂度是O(N * log N),并不符合题目要求
    • 思路一:0 ~N个数字全部加起来再减去数组中的所有数字加起来,得到的结果就是缺失的那个数,时间复杂度O(N)
    • 思路三:内存映射,将数组元素值出现的次数放在对应的一个数组下标位置,时间复杂度是O(N)
    • 思路四:异或,将m与0 ~ numsize个数字和0 ~ numsize数组元素异或,最后再与数组长度异或,时间复杂度是O(N)
    //实现思路四:int missingNumber(int* nums, int numsSize){     int m = 0;    int i = 0;    while(i < numsSize)    {         m ^= i;        m ^= nums[i++];    }        m ^= numsSize;    return m;}
    

    旋转数组
    链接: [link](javascript:void(0)).
    题目描述:

    给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数
    img
    实现思路:
    数组元素整体逆置,【0,numsSize - 1】
    左区间逆置,【0,k - 1】
    右区间逆置,【k,numsize - 1】

    //逆置数组void reverse(int* nums1,int *nums2){    while(nums1 < nums2)   {        int tmp = *nums1;       *nums1 = *nums2;       *nums2 = tmp;       ++nums1;       --nums2;   }   }void rotate(int* nums, int numsSize, int k){     if(k >= numsSize)    k %= numsSize;        reverse(nums, nums + numsSize - 1);    reverse(nums,nums + k - 1);    reverse(nums + k,nums + numsSize - 1);   }
    整体逆置,【0,numsSize - 1】
    > 左区间逆置,【0,k - 1】
    > 右区间逆置,【k,numsize - 1】
    
    
    
    
    
    

    //逆置数组void reverse(int* nums1,int *nums2){ while(nums1 < nums2) { int tmp = *nums1; *nums1 = *nums2; nums2 = tmp; ++nums1; --nums2; } }void rotate(int nums, int numsSize, int k){ if(k >= numsSize) k %= numsSize; reverse(nums, nums + numsSize - 1); reverse(nums,nums + k - 1); reverse(nums + k,nums + numsSize - 1); }

    展开全文
  • 算法设计目标与时间复杂度与空间复杂度.ppt
  • 对时间复杂度和空间复杂度进行超级详细的讲解
  • 算法空间复杂度详细介绍


    上一篇博客中我们学习了时间复杂度:需要的小伙伴请点击:

    https://blog.csdn.net/qq_43355165/article/details/122644530

    概念定义

    空间复杂度涉及的空间类型有:

    • 输入空间:存储输入数据所需的空间大小;
    • 暂存空间: 算法运行过程中,存储所有中间变量和对象等数据所需的空间大小;
    • 输出空间: 算法运行返回时,存储输出数据所需的空间大小;
      通常情况下,空间复杂度指在输入数据大小为N时,算法运行所使用的暂存空间 + 输出空间的总体大小。
      在这里插入图片描述
      而根据不同来源,算法使用的内存空间分为三类:

    指令空间:

    编译后,程序指令所使用的内存空间。

    数据空间:

    算法中的各项变量使用,包括:声明的变量、变量、动态数组、动态对象等使用的内存空间。

    class Node:
    	def __init__(self, val):
    		self.val = val
    		self.next = None
    	def algorithm(N):
    		num = N        # 数组
    		nums = [0] * N # 动态数组
    		node = Node(N) # 动态对象
    

    栈帧空间:

    程序调用函数是基于栈实现的,函数在调用期间,占用常量大小的栈帧空间,直至返回后释放。如以下代码所示,在循环中调用函数,每轮调用test()返回后,栈帧空间已被释放,因此空间复杂度仍为O(1)。

    def test():
    	return 0
    def algorithm(N):
    	for _ in range(N):
    		test()
    

    算法中,栈帧空间的累计常出现于递归调用。如以下代码所示,通过递归调用,会同时存在N个未返回的函数 algorithm(),此时累计使用O(N)大小的栈帧空间。

    def algorithm(N):
    	if N <= 1: return 1
    	return algorithm(N - 1) + 1
    

    符号表示

    通常情况下,空间复杂度统计算法在“最差情况”下使用的空间大小,以体现算法运行所需预留的空间量,使用符号O表示。
    最差情况有两层含义,分别为最差输入数据、算法运行中的最差运行点。例如以下代码:

    • 最差输入数据:当N<=10时,数组nums的长度恒定为10,空间复杂度为O(10) = O(1);当N > 10时,数组nums长度为N,空间复杂度为O(N);因此,空间复杂度应为最差输入数据情况下的O(N)。
    • 最差运行点:在执行nums = [0] * 10时,算法仅使用O(1)大小的空间;而当执行nums = [0] * N时,算法使用O (N)的空间;因此,空间复杂度应为最差运行点的O(N)。
    def algorithm(N):
    	num = 5			   # O(1)
    	nums = [0] * 10    # O(1)
    	if N > 10:
    	 	nums = [0] * N # O(N)
    

    常见种类

    根据从小到大排列,常见的算法空间复杂度有:
    O(1) < O(logN) < O(N) < O(N 2) < O(2N)
    在这里插入图片描述

    示例解析

    对于以下所有示例,设输入数据大小为正整数N,节点类Node、函数test()如以下代码所示。

    class Node:
    	def __init__(self, val):
    		self.val = val
    		self.next = Node
    	# 函数 test()
    def test():
    	return 0
    

    常数O(1):

    普通常量、变量、对象、元素数量与输入数据大小N无关的集合,皆使用常数大小的空间。

    def algorithm(N):
    	num = 0
    	nums = [0] * 10000
    	node = Node(0)
    	dic = {0: '0'}
    

    如以下代码所示,虽然函数test()调用了N次,但每轮调用后test()已返回,无累计栈帧空间使用,因此空间复杂度仍为O(1)。

    def algorithm(N)
    	for _ in range(N):
    		test()
    

    线性O(N)

    元素数量与N呈线性关系的任意类型集合(常见于一维数组、链表、哈希表等),皆使用线性大小的空间。

    def algorithm(N):
    	nums_1 = [0] * N
    	nums_2 = [0] * (N // 2)
    
    	nodes = [Node(i) for i in range(N)]
    	
    	dic = {}
    	for i in range(N):
    		dic[i] = str(i)
    

    如下图与代码所示,此递归调用期间,会同时存在N个未返回的algorithm()函数,因此使用O(N)大小的栈帧空间。

    def algorithm(N):
    	if N <= 1: return 1
    	return algorithm(N - 1) + 1
    

    在这里插入图片描述

    平方O(N2):

    元素数量与N呈平方关系的任意类型集合(常见于矩阵),皆使用平方大小的空间。

    def algorithm(N):
    	num_matrix = [[0 for j in range(N)] for i in range(i)]
    	node_matrix = [[Node(j) for j in range(N)] for i in range(N)]
    

    如下图与代码所示,递归调用时同时存在 N 个未返回的algorithm()函数,使用 O(N) 栈帧空间;每层递归函数中声明了数组,平均长度为N/2 ,使用 O(N)空间;因此总体空间复杂度为 O(N2)。

    def algorithm(N):
        if N <= 0: return 0
        nums = [0] * N      # O(N)
        return algorithm(N - 1)
    

    在这里插入图片描述

    指数O(2N) :

    指数阶常见于二叉树、多叉树。例如,高度为N满二叉树的节点数量为2N,占用O(2N)大小的空间;同理,高度为N满m叉树的节点数量为mN,占用O(mN) = O(2N)大小的空间。
    在这里插入图片描述

    对数O(logN) :

    对数阶常出现于分治算法的栈帧空间累计、数据类型转换等,例如:

    • 快速排序 ,平均空间复杂度为 Θ(logN) ,最差空间复杂度为 O(N) 。拓展知识:通过应用 Tail Call Optimization ,可以将快速排序的最差空间复杂度限定至O(N)
    • 数字转化为字符串 ,设某正整数为 N ,则字符串的空间复杂度为 O(logN) 。推导如下:正整数 N 的位数为 log10N ,即转化的字符串长度为log10N,因此空间复杂度为 O(logN)

    时空权衡

    对于算法的性能,需要从时间和空间的使用情况来综合评价。优良的算法应具备两个特性,即时间和空间复杂度皆较低。而实际上,对于某个算法问题,同时优化时间复杂度和空间复杂度是非常困难的。降低时间复杂度,往往是以提升空间复杂度为代价的,反之亦然。

    由于当代计算机的内存充足,通常情况下,算法设计中一般会采取「空间换时间」的做法,即牺牲部分计算机存储空间,来提升算法的运行速度。

    以 LeetCode 全站第一题 两数之和 为例,「暴力枚举」和「辅助哈希表」分别为「空间最优」和「时间最优」的两种算法。

    方法一:暴力枚举

    时间复杂度 O(N2) ,空间复杂度O(1) ;属于「时间换空间」,虽然仅使用常数大小的额外空间,但运行速度过慢。

    class Solution:
        def twoSum(self, nums: List[int], target: int) -> List[int]:
            for i in range(len(nums) - 1):
                for j in range(i + 1, len(nums)):
                    if nums[i] + nums[j] == target:
                        return i, j
            return
    

    方法二:辅助哈希表

    时间复杂度 O(N),空间复杂度 O(N);属于「空间换时间」,借助辅助哈希表 dic ,通过保存数组元素值与索引的映射来提升算法运行效率,是本题的最佳解法。

    class Solution:
        def twoSum(self, nums: List[int], target: int) -> List[int]:
            dic = {}
            for i in range(len(nums)):
                if target - nums[i] in dic:
                    return dic[target - nums[i]], i
                dic[nums[i]] = i
            return []
    

    在 LeetCode 题目中,「输入空间」和「输出空间」往往是固定的,是必须使用的内存空间。因希望专注于算法性能对比,本 LeetBook 的题目解析的空间复杂度仅统计「暂存空间」大小。

    本文转自:https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/r8ytog/

    展开全文
  • 什么是时间复杂度与空间复杂度

    千次阅读 多人点赞 2022-03-02 08:47:16
    目录算法效率时间复杂度概念大O的线性表示法时间复杂度举例空间复杂度空间复杂度的定义空间复杂度举例 时间复杂度与空间复杂度是用来分析一个算法的效率的。 算法效率 算法效率分析分为两种:第一种是时间效率,第二...


    时间复杂度与空间复杂度是用来分析一个算法的效率的。

    算法效率

    算法效率分析分为两种:第一种是时间效率,第二种是空间效率。时间效率被称为时间复杂度,而空间效率被称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度,而空间复杂度主要衡量一个算法所需要的额外空间,在计算机发展的早期,计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展,计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

    时间复杂度

    概念

    时间复杂度的定义:在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。 一个算法执行所耗费的时间理论上来说是算不出来的,因为它不仅仅与你写的算法有关,还与运行这个算法的机器也有关系,如果你的机器很好,那么你所耗费的时间就可能会更少,所以,一个算法耗费的时间是需要放在机器上实际测验才能知道的,但是我们总不能每个算法都拿来上机测试,来记录该算法的时间,所以我们就有了时间复杂度这样的分析方式。
    一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复杂度。

    大O的线性表示法

    大O符号(Big O notation):是用于描述函数渐进行为的数学符号。
    我们来计算一下下面代码的时间复杂度

    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);
    }
    

    这个函数在调用的过程中使用了三个for循环和一个while循环,每循环一次我们说它进行了一次基本操作。那么这个函数执行基本操作的次数为F(N)=N²+2*N+10
    那么我们如何用大O的线性表示法来表示这个函数的时间复杂度呢?

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

    按照上面的规则,那么上述代码的时间复杂度就为O(N²)。
    我们发现,通过上面的规则,我们就使用N²来代替了N²+2*N+10,我们为什么要这样规定呢,我们以上面的表达式为例,当N为不同的值时,表达式的结果为多少

    N=100 F(N)=10210
    N=1000 F(N)=1002010
    N=10000 F(N)=100020010

    我们发现,当N不断变大时,表达式的值也不断变大,而对表达式的结果影响最大的一项就是这个表达式中阶数最高的那一项。

    那我们为什么只保留对结果影响最大的那一项呢?我们知道时间复杂度描述的对象是一个算法,而不是某一次的运算,那么当我们使用这个算法并向里面传入一个能够影响算法基本操作执行次数的变量时,我们并不能确定我们输入的N的值是多少,N就有可能是任何值,当N比较小时,也许别的项与最高阶项的结果差距并没有那么大,但是当N的值越来越大时,最高阶项的值与其他项的值的差距也就越来越大了,我们还是以上面的代码为例,当我们的N在不断的变大时,因为其余项对结果的影响相对来说比较小,那么我们就可以忽略他们对结果的影响,只保留对结果影响最大的那一项来表示我们的时间复杂度。

    那么为什么我们要用1来表示所以的常数呢,这是因为计算机的运行速度是非常快的,每秒可能就可以执行上亿此的运算,那么常数次的执行次数与我们计算机的运算速度相比,可能与执行一次的运行速度相差不会太大,所以我们就使用1来代替所有的常数项,那么只有循环次数为常数的算法的时间复杂度相应的就是O(1)。

    去掉与最高阶项相乘的常数的原因也是因为对结果影响最大的是这个最高阶项,而不是这个最高阶项前面的系数,所以也要把它去掉。

    时间复杂度举例

    现在我们就大概明白了如何来计算一个算法的时间复杂度,下面我们来看几个代码练习一下。

    void Func(int N, int M) 
    {
        int count = 0;
        for (int k = 0; k < M; ++k) 
        {
            ++count;
        }
        for (int k = 0; k < N; ++k) 
        {
            ++count;
        }
        printf("%d\n", count);
    }
    

    在这个算法中,我们在传入了两个变量,导致两个循环的循环次数分别由两个变量来决定,这时我们认为时间复杂度为O(N+M),因为我们不知道M和N谁大,所以我们谁都无法省略。

    void my_strchr(char* str,char c)
    {
        while (*str != '\0')
        {
            if (*str == c)
            {
                return str;
            }
            str++;
        }
    }
    

    这是一个简单的字符串查找函数,在这个算法中,并没有一个变量值来描述我们需要进行循环的次数,而觉得我们循环次数的是被查找字符串的长度,在时间复杂度的计算中,我们通常假设数组或字符串的长度为N,还有一个问题是这个算法中即使我们知道了字符串的长度但是我们执行循环的次数也是不一定的,因为我们不知道什么时候能够在字符串中找到我们寻找的元素,可能我们在第一个位置就找到了,也有可能我们要遍历整个字符串在最后一个元素的位置才能找到,出现这种情况时默认时间复杂度要以最坏的情况为准,即O(N)。

    冒泡排序的时间复杂度?

    void BubbleSort(int* a, int n) 
    {
        assert(a);
        for (size_t end = n; end > 0; --end) 
        {
            int exchange = 0;
            for (size_t i = 1; i < end; ++i)
            {
                if (a[i - 1] > a[i])
                {
                    Swap(&a[i - 1], &a[i]);
                    exchange = 1;
                }
            }
            if (exchange == 0)
                break;
        }
    }
    

    上面的是一个冒泡排序的函数,我们知道在进行冒泡排序时,我们首先要进行N次排序,然后在每次排序时,我们又要遍历这个数组,但是我们每进行一次排序,在下一次排序时我们就可以少遍历一个元素,所以我们可以得到实际的运算次数F(N)=N+(N-1)+(N-2)……+2+1。这是一个等差数列,结果化简为F(N)=N*(N+1)/2,所以时间复杂度为O(N²)

    二分查找的时间复杂度?

    int BinarySearch(int* a, int n, int x) 
    {
        assert(a);
        int begin = 0;
        int end = n - 1;
        while (begin < end) 
        {
            int mid = begin + ((end - begin) >> 1);
            if (a[mid] < x)
                begin = mid + 1;
            else if (a[mid] > x)
                end = mid;
            else
                return mid;
        }
        return -1;
    }
    

    上面的是一个二分查找函数的代码,我们知道二分查找是在一个有序数组中查找某一个元素时的比较高效的方法,在进行二分查找时,我们每次都取数组的中间值,然后再根据中间值与查找值的大小来确定我们要查找的元素在那一半,然后在对找到的哪一半数组进行重复的操作,直到找到我们需要的元素,使用二分查找时,最坏的情况是我们把数组除的只剩最后一个元素,这时表达式为N÷2÷2÷2÷2…÷2÷2=1我们把这个式子换算一下为
    N=1×2×2×2…×2×2我们每相乘一次,就进行了一次基本操作,所以上式中我们一共进行了log₂N次,所以时间复杂度为O(log₂N)。

    递归的时间复杂度?

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

    上面的代码是一个计算斐波那契数列的函数,使用的是递归的方法,我们知道递归的方法来计算斐波那契数列是非常低效的,最好还是使用循环的方法,但是递归的时间复杂度是多少呢?
    我们知道每一次调用这个函数时,我们的时间复杂度是一个常数,那么这个递归的时间复杂度就是我们一共调用了多少次函数,现在我们来分析一下我们到底调用了多少次这个函数。
    其调用结构如图所示
    在这里插入图片描述
    当我们输入N时,函数会进行两调用,然后不断地调用,其调用的结果如图所示,在右下角是有一个空缺区域的,但是我们可以把这一块空缺的区域看作一个常数,假设它是满的,那么我们执行调用的总次数为F(N)=2⁰+2¹+2²+…+2N-1=2N-1,所以该算法的时间按复杂度为O(2N)。
    由以上的计算我们就可以发现用递归来算斐波那契数的算法的时间复杂度太高了,也就说明了这个算法的低效。

    空间复杂度

    空间复杂度的定义

    空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似,也使用大O渐进表示法。

    空间复杂度举例

    冒泡排序的空间复杂度?

    void BubbleSort(int* a, int n) 
    {
         assert(a);
         for (size_t end = n; end > 0; --end)
         {
             int exchange = 0;
             for (size_t i = 1; i < end; ++i)
             {
                 if (a[i-1] > a[i])
                 {
                     Swap(&a[i-1], &a[i]);
                     exchange = 1;
                 }
             }
             if (exchange == 0)
             break;
         }
    }
    

    还是刚刚冒泡排序的代码,我们刚刚计算了它的时间复杂度,现在再来看一下它的空间复杂度,根据定义我们知道,空间复杂度是用来估算占用空间的大小的,那么我们就可以根据算法中创建的变量的个数来表示算法的空间复杂度,这个冒泡排序算法创建了3个变量,根据大O的渐进表示法的规则,该算法的空间复杂度就为O(1)。

    循环方法计算斐波那契数列的空间复杂度?
    在计算时间复杂度时,我们知道使用递归的方法计算斐波那契数是一种非常低效的方法,而使用循环的方法就高效一些,那么循环的方法的空间复杂度又为多少?

    long long* Fibonacci(size_t n) 
    {
        if (n == 0)
            return NULL;
    
        long long* fibArray =(long long*)malloc((n + 1) * sizeof(long long));
        fibArray[0] = 0;
        fibArray[1] = 1; for (int i = 2; i <= n; ++i)
        {
            fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
        }
        return fibArray;
    }
    

    这就是循环方法计算斐波那契数的代码,我们发现在这个算法中,我们使用malloc开辟了一块元素个数为n+1的空间,那就相当于创建了n+1个变量,根据大O的线性表示法,该算法的空间复杂度就为O(N)。
    那么我们使用递归的方法时的空间复杂度又是多少呢

    long long Factorial(size_t N) 
    {
         return N < 2 ? N : Factorial(N-1)*N; 
    }
    

    我们知道在调用函数时,是会创建栈帧的,简单来说就是我们每调用一次函数,就会为调用的那个函数创建一块空间,在计算递归算法的空间复杂度时,我们可以认为每次函数调用时都会创建常数个变量,那么影响我们算法空间复杂度的就是我们调用递归的次数,那么以上面的算法为例,该算法的空间复杂度就是O(N)。递归算法的空间复杂度通常是递归的深度

    空间复杂度一般只有两种情况:
    创建了常数个变量:O(1)
    创建了N个变量:O(N)

    以上就是本篇的全部内容。

    展开全文
  • 数据结构>时间复杂度及空间复杂度

    多人点赞 热门讨论 2022-03-03 23:08:11
    1.3、空间复杂度 二、计算 2.1、大O的渐进表示法 2.2、时间复杂度计算 例题: 2.3、空间复杂度计算 例题 三、有复杂度要求的习题 一、概念 1.1、算法效率 算法效率分析分为两种:第一种是时间效率...
  • 一、空间复杂度定义 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。 一个算法在计算机存储器上所占用的存储空间,包括程序代码所占用的空间,输入数据所占用的空间和辅助变量所...
  • 递归算法的时间与空间复杂度分析

    千次阅读 2022-04-15 11:25:28
    本篇讲通过求斐波那契数列和二分法再来深入分析一波递归算法的时间和空间复杂度,细心看完,会刷新对递归的认知!
  • 算法(Algorithm)是指用来操作数据、解决...空间维度:是指执行当前算法需要占用多少内存空间,我们通常用「空间复杂度」来描述。 因此,评价一个算法的效率主要是看它的时间复杂度和空间复杂度情况。然而,有的时候
  • 1,什么是时间复杂度? 一个问题的规模是n,解决这一问题所需算法所需要...空间复杂度需要考虑在运行过程中为局部变量分配的存储空间的大小,它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配
  • 想要学好算法,必须要掌握如何分析一个算法的时间复杂度和空间复杂度,只有自己会分析这两个个衡量算法主要性能的标准,才能更好的写出性能优秀的算法,复杂度同时也可以分为最好时间复杂度,最坏时间复杂度,平均...
  • 数据结构001 - 时间复杂度与空间复杂度
  • 一、数据结构前言 数据结构:内存中存储管理数据的结构 数据结构和数据库的区别:本质都是存储管理数据 数据结构--在内存中存储管理数据 数据库--在...是从时间和空间两个维度来衡量的,即时间复杂度和空间复杂度
  • 空间复杂度分析

    2022-04-15 08:57:25
    空间复杂度分析1.空间复杂度定义 1.空间复杂度定义 是对一个算法在运行过程中占用内存空间大小的量度,记做S(n)=O(f(n))S(n)=O(f(n))S(n)=O(f(n))。 空间复杂度(Space Complexity)记作S(n)S(n)S(n)依然使用大OOO来...
  • 【数据结构学习之路】算法的时间复杂度和空间复杂度 文章目录【数据结构学习之路】算法的时间复杂度和空间复杂度(1)算法效率(2)时间复杂度的计算1)什么是时间复杂度2)大O渐进表示法(估算)3)时间复杂度计算...
  • 算法的时间复杂度和空间复杂度

    千次阅读 2022-03-09 18:56:06
    空间复杂度 常见时间复杂度以及复杂度oj练习 一. 算法的效率 1. 如何衡量一个算法的好坏 如何衡量一个算法的好坏呢?比如对于以下斐波那契数列: long long Fib(int N) { if(N < 3) return 1; return...
  • 文章目录前言一、时间复杂度、空间复杂度的定义二、借助案例, 理解时间、空间复杂度1. 时间复杂度案例:几种常见的时间复杂度多块代码的时间复杂度对数阶和相加情况2. 空间复杂度案例:常见的空间复杂度3. 复杂度...
  • 时间复杂度和空间复杂度(超详细)

    万次阅读 多人点赞 2020-08-11 17:11:00
    文章目录算法的时间复杂度和空间复杂度复杂度的分析一. 时间维度事后统计法事前分析估算的方法时间复杂度(1)时间频度(2)时间复杂度大O符号表示法常见的时间复杂度量级常数阶O(1)线性阶O(n)对数阶O(logN)线性对数阶O...
  • 文章目录1.算法效率2.时间复杂度大O渐近表示法3.空间复杂度 1.算法效率 算法效率分析分为两种:第一种是时间效率,第二种是...计算时间复杂度和空间复杂度时,为了估算一个算法的耗时情况,不需要计算出精确的执行次
  • 时间复杂度与空间复杂度1.算法的复杂度:2.时间复杂度:1.大O表示法:2.大O推导方法:3.一些常见的大O运行时间:3.空间复杂度:4.个别特殊举例:1.斐波那契数列的时间和空间复杂度2.二分法的时间复杂度和空间复杂度 ...
  • 学习算法的时间复杂度和空间复杂度一篇就够了

    多人点赞 热门讨论 2022-04-08 19:09:26
    学习算法的时间复杂度和空间复杂度一篇就够了 算法的时间复杂度分析 大O记法 常见的大O阶 线性阶 平方阶 立方阶 对数阶 常数阶 函数调用的时间复杂度分析 最坏情况 算法的空间复杂度分析 java中常见内存占用 算法的...
  • 解析空间复杂度

    2022-03-13 10:41:44
    概念:空间复杂度是一个数学函数表达式,是对一个算法运行过程中临时占用储存空间大小的量度。 空间复杂度计算的是变量的个数。可以使用大O渐近法。 注意:函数运行时所需要的栈空间(储存参数。局部变量。一些...
  • 时间复杂度和空间复杂度前言算法效率时间复杂度1.时间复杂度的概念2.大O的渐进(估算)表示法推导大O阶方法(重点!!!):另外有些算法的时间复杂度存在最好、平均、和最坏情况(重点!!!):3.常见时间复杂度计算...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 520,461
精华内容 208,184
关键字:

空间复杂度

友情链接: YYFapp.zip