【数据结构手札】空间复杂度详解：概念 | 习题

🌈个人主页：聆风吟
🔥系列专栏：数据结构手札
🔖少年有梦不应止于心动，更要付诸行动。

文章目录

• 📚专栏订阅推荐
• 📋往期回顾：复杂度概念
• 📋往期回顾：大O的渐进表示法
• 一. ⛳️算法的空间复杂度
• 二. ⛳️常见空间复杂度计算举例
  • 1️⃣实例一
  • 2️⃣实例二
  • 3️⃣实例三
  • 4️⃣实例四
• 📝全文总结

📚专栏订阅推荐

📋往期回顾：复杂度概念

算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。

时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

📋往期回顾：大O的渐进表示法

大O符号（big O notation）：是用于描述函数渐进行为的数学符号。

推导大O阶方法：

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

一. ⛳️算法的空间复杂度

算法空间复杂度的定义：

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

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

二. ⛳️常见空间复杂度计算举例

1️⃣实例一

int**fun(int n){int** s =(int**)malloc(n *sizeof(int*));for(size_t i =0; i < n;++i){ s[i]=(int*)malloc((i +1)*sizeof(int));}return s;}

解析： 实例1在此处开辟的是一个二维数组，数组有n行，每行分别有1,2,3,…n列，所以是n(n + 1)/2个元素空间，空间复杂度为O(n^2)

2️⃣实例二

// 计算BubbleSort的空间复杂度？voidBubbleSort(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;}}

解析： 实例2使用了常数个额外空间，分别是[ end，exchange，i ]。根据大O阶的推导方法很容易得出，BubbleSort空间复杂度为 O(1)

3️⃣实例三

// 计算Fibonacci的空间复杂度？// 返回斐波那契数列的前n项longlong*Fibonacci(size_t n){if(n ==0)returnNULL;longlong* fibArray =(longlong*)malloc((n +1)*sizeof(longlong)); fibArray[0]=0; fibArray[1]=1;for(int i =2; i <= n;++i){ fibArray[i]= fibArray[i -1]+ fibArray[i -2];}return fibArray;}

解析：实例3动态开辟了N+1个空间，根据大O阶的推导方法很容易得出，Fibonacci空间复杂度为 O(N)。

4️⃣实例四

// 计算阶乘递归Fac的空间复杂度？longlongFac(size_t N){if(N ==0)return1;returnFac(N -1)* N;}

解析：实例4递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N)。

🎯递归算法的空间复杂度 = 单次递归的空间复杂度 * 递归次数

📝全文总结

本文系统性地讲解了算法空间复杂度的核心知识，旨在帮助读者建立一套分析算法效率的完整框架。

今天的干货分享到这里就结束啦！如果觉得文章还可以的话，希望能给个三连支持一下，聆风吟的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是作者前进的最大动力！