数据结构之空间复杂度详解

简介: 在上一篇文章我们了解了时间复杂度,今天我们就从空间的角度来分析一个算法。

前言

在上一篇文章我们了解了时间复杂度,今天我们就从空间的角度来分析一个算法。


1. 空间复杂概念

空间复杂度也是一个数学表达式,是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似,也使用大O渐进表示法。(大O渐进法在时间复杂度的介绍中有详细解释,这里就不具体说明)


注意:函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了,因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。


2. 实例演示介绍

2.1 冒泡排序的空间复杂度分析

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


根据空间复杂度的判断条件,我们要关注的是额外的创建的空间,那么这里为实现该代码逻辑的运行额外创建的变量有end, i,以及exchange,很明显这里是一个常数的量级,那么这里的空间复杂度是O(1)。


2.2  循环判断斐波那契函数的第n项

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

这里我们可以看到,此处用动态内存开辟,开辟了(n+1) long long类型大小的空间,而且没看到比O(n)更大量级的额外空间开辟,那么很明显的得到,此处的空间复杂度是O(N)。


2.3 计算阶乘递归Fac的空间复杂度

在讲解这个程序的空间复杂度,首先这里要和大家简单的介绍一个概念,也就是一个函数在使用时,操作系统会为这个函数开辟一块空间,在使用结束后销毁,这个具体细节我会在后续对函数栈帧的创建与销毁中为大家详细介绍。

long long Fac(size_t N)
{
 if(N == 0)
 return 1;
 return Fac(N-1)*N;
}

image.png



对于上面的递归调用和结束,逻辑如上,只有在最后一次递归结束后才会逐渐向上结束函数Fac(N),那么在这个过程中,Fac(N)不断向下创建的空间是不断叠加不会销毁的,所以这里由递归导致的空间复杂度是O(N)。


相关文章
|
7月前
|
存储 算法
数据结构——lesson1时间复杂度和空间复杂度
数据结构——lesson1时间复杂度和空间复杂度
|
7月前
|
机器学习/深度学习 存储 缓存
数据结构从入门到精通——算法的时间复杂度和空间复杂度
算法的时间复杂度和空间复杂度是评估算法性能的两个重要指标。时间复杂度主要关注算法执行过程中所需的时间随输入规模的变化情况,而空间复杂度则关注算法执行过程中所需的最大存储空间或内存空间。
324 0
|
7月前
|
机器学习/深度学习 存储 算法
数据结构 | 算法的时间复杂度和空间复杂度【详解】(二)
数据结构 | 算法的时间复杂度和空间复杂度【详解】(二)
|
7月前
|
机器学习/深度学习 存储 算法
数据结构 | 算法的时间复杂度和空间复杂度【详解】(一)
什么是数据结构? 数据结构(Data Structure)是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合。
|
6月前
|
存储 算法 C语言
数据结构中的空间复杂度
优化空间复杂度对于提升程序性能和资源利用率至关重要,特别是在资源受限的环境(如嵌入式系统和移动设备)中。高效的数据结构和算法设计可以显著提升程序的执行效率和可扩展性。 综上所述,理解和优化空间复杂度是设计高效数据结构和算法的关键。通过分析常见数据结构的空间复杂度,并结合实际代码示例,我们可以更好地理解这一重要概念,并在实际编程中应用这些知识。希望本文能帮助你更好地掌握空间复杂度及其在数据结构中的应用。
46 2
|
2月前
|
机器学习/深度学习 存储 算法
【初阶数据结构】算法效率大揭秘 | 时间与空间复杂度的深度剖析
【初阶数据结构】算法效率大揭秘 | 时间与空间复杂度的深度剖析
|
2月前
|
算法
[数据结构] -- 时间复杂度和空间复杂度
[数据结构] -- 时间复杂度和空间复杂度
15 0
|
7月前
|
机器学习/深度学习 算法 存储
[数据结构]——算法的时间复杂度和空间复杂度
[数据结构]——算法的时间复杂度和空间复杂度
|
4月前
|
存储 算法
【数据结构】——时间复杂度与空间复杂度
【数据结构】——时间复杂度与空间复杂度
|
6月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题