2025年算法---------空间复杂度

科技前沿 • 2025-03-06 21:42 • 阅读 35

大家好，我是讯享网，很高兴认识大家。

空间复杂度：

空间开销（内存开销）与问题规模n之间的关系

例1：

我们依然选择上篇文章中将时间复杂度用到的实例：

void loveyou(int n)//n为问题规模 { 
    int i = 1; while (i <= n) { 
    i++; printf("I LOVE YOU%d", i); } printf("I LOVE YOU More than %d\n", n); }

讯享网

将该程序放入计算机中，它在内存中，存储形式如下所示：
在这里插入图片描述
讯享网

由此可知，无论问题规模怎么变化，算法运行所需的内存空间都是固定的常量，算法空间复杂度为S(n)=O(1),这也被称为算法原地工作。

算法原地工作是指：算法所需内存空间为常量。

但并不都是无论问题规模怎么变化，算法运行所需的内存空间都是固定的常量的这种情况。

例2：

我们依然选择上篇文章中将时间复杂度用到的实例：

讯享网void loveyou(int n) { 
    printf("I LOVE YOU More than %d\n", n); int i = 1; while (i < n) { 
    if (Flag[i] == n) printf("I LOVE YOU%d\n", i); } } //Flag数组乱序存放1-n这些数 int Flag[n]={ 
   1.....n}; loveyou(Flag,n);

将该程序放入计算机中，它在内存中，存储形式如下所示：
在这里插入图片描述
此时，空间复杂度就和时间规模n有关联，由此可得算法空间复杂度为S（n）=O(4n+8)=O(n)

例3：

void test(int n) { 
    int flag[n][n]; int i; ...... }

对于这个程序代码，我们依然可以根据上面的分析过程进行分析，不过需要提醒的是：

讯享网int flag[n][n];//所占内存空间为：4n*n,而不是16n*n //原因：该数组被定义为整形数组，那么该数组一个元素所占据的空间是4B,数组元素的个数有n*n个

由此可得该算法的空间复杂度为：S(n)=4nn+8=O(nn)

例4：

void test(int n) { 
    int flag[n][n]; int other[n]; int i; }

对于这个程序代码，我们分析得出算法空间复杂度为：S(n)=4nn+n+8=O(nn)+O(n)+O(1)=O(n*n).

总结：

程序代码在内存中所占的空间是大小不变的，因此在分析空间复杂度时，只需要分析变量所占的空间，计算出算法空间复杂度后，处理方式依然和时间复杂度相同，保留高阶，忽略低阶（不懂得可以参考上篇文章）

函数递归调用带来的内存开销：

每次调用所需内存空间的大小相同：

举例：

讯享网void loveyou(int n) { 
    int a, b, c;//每次调用，a,b,c的值虽然没有改变，但存储位置法会随着n变化 if (n > 1) { 
    loveyou(n - 1); } printf("I love you %d\n", n); } int main() { 
    loveyou(5); }

分析过程如下：
在这里插入图片描述由此，我们可以得出一个结论：空间复杂度=递归调用的深度

void loveyou(int n) { 
    int flag[n]; if (n > 1) { 
    loveyou(n - 1); } printf("I love you %d\n", n); } int main() { 
    loveyou(5); }

在这里插入图片描述
与上面那个例子不同的是：该实例中的int flag[n]中的n,也会随着调用次数而变化,因此，每一级数组的长度是不同的，这也导致，每一级的调用空间是不同的。

因此，各级调用的空间复杂程度为:1+2+3+4+5+…+n=[n(1+n)]/2=1/2nn+1/2n,故S(n)=O(n*n).

2025年算法---------空间复杂度

空间复杂度：

总结：

函数递归调用带来的内存开销：

每次调用所需内存空间的大小相同：

相关推荐