刷题时遇到了内存超界？分享一点小技巧

TechFlow-承志

发布于 2022-12-22 11:03:10

8160

发布于 2022-12-22 11:03:10

文章被收录于专栏：TechFlow

作者 | 梁唐

出品 | 公众号：Coder梁（ID：Coder_LT）

大家好，我是梁唐。

今天我们来聊聊算法的空间复杂度，相比于时间复杂度，以空间复杂度出发的算法题相对不太多。重要性相对没那么大，但同样也是非常重要的基础知识，需要有一定的认知。

空间复杂度的定义

空间复杂度的定义和时间复杂度类似，时间复杂度描述的是程序运行时间和问题规模之间的关系。空间复杂度描述的就是程序运行时消耗的内存与问题规模的关系，也同样使用大O表示法来表示。

如果对大O表示法或者时间复杂度不太熟悉的话，可以翻看一下之前的文章。

这里要特别强调一下，空间复杂度仅考虑是程序运行时消耗的内存，而不会考虑编译之后可执行文件的大小或者代码本身的大小。另外和时间复杂度不同的是，我们在程序里申请的内存是可以释放的。因此在推导空间复杂度时仅仅需要考虑程序运行时占用内存最大时刻的情况即可。

内存使用技巧

一般情况下在算法竞赛场景当中，内存的使用主要有三个来源。分别是数组、结构体和容器。其中容器消耗的内存是动态的，根据程序运行时填入的数据多少而变化。而数组和结构体则是静态的，我们在声明时就可以知道它们占用的内存大小。

关于内存的使用，这里有几个技巧。

不要在局部声明过大的数组

在C++当中，在函数内声明的变量都是局部变量，局部变量是有大小限制的。

比如如下代码：

#include<stdio.h>

void test() {
    int a[1000000];
}

int main() {
    test();
    printf("hello world"); 
    return 0;
}

在我的电脑上编译可以通过，但运行时没有结果的。原因就是因为我们在test中创建了过大的数组，导致程序崩溃。

局部变量的大小限制取决于系统以及编译器，可能会出现同样的代码在有些编译器上可以运行，但有些不能的情况。如果事先不知道，想要debug是非常困难的。

计算内存

最后，使用全局变量我们可以事先计算好内存消耗，可以在提交之前就预判是否满足题目要求。

比如我们开辟一个长度为1000w的int数组，它会消耗多少内存呢？

很简单，每一个int占据32位，即4个字节。长度为一千万的数组，占用的就是4000w字节。我们知道1KB=1024B（字节），1MB=1024KB，所以1MB大约等于100w字节。所以4000w字节，占用内存大约在40MB左右。

很多职业选手更喜欢使用全局变量，而非容器。因为职业选手对于数组的内存消耗非常熟悉了，当前的问题最坏的情况需要使用多少空间？多大的数组会占用多少内存？这些问题，他们都心里清晰有数。因此比赛的时候游刃有余，几乎完全不用担心空间溢出的问题。

递归时的空间复杂度

由于程序使用的内存相比于耗时来说要好判断很多，毕竟只和我们开辟的数组以及声明的变量有关。因此大多数情况下都可以很直观地得到答案。

唯一值得说道的是递归时的情况，递归算法当中消耗的内存是递归的最大深度乘上每次递归单次的消耗。但有的时候，每次递归开辟的内存是不同的，这样的方式可能不太好计算。还是以归并排序举例：

def merge_sort(arr):
    n = len(arr)
    # 当长度小于等于1，说明天然有序
    if n <= 1:
        return arr
    mid = n // 2
    # 通过切片将数组一分为二，递归排序左边以及右边部分
    L, R = merge_sort(arr[: mid]), merge_sort(arr[mid: ])
    n_l, n_r = len(L), len(R)
    
    # 数组当中插入标兵
    L.append(sys.maxsize)
    R.append(sys.maxsize)
    new_arr = []
    i, j = 0, 0
    
    # 归并已经排好序的L和R
    while i < n_l or j < n_r:
        if L[i] <= R[j]:
            new_arr.append(L[i])
            i += 1
        else:
            new_arr.append(R[j])
            j += 1
    return new_arr

很明显，这是一个递归函数，在这个函数当中，我们会将传入的数组arr分成两个部分分别进行归并排序之后再合并。在这个过程当中，我们创建了两个局部变量L和R来分别存储左右两边的部分。

L和R就是我们在递归当中新开辟的，会额外地消耗内存。但是随着递归的进行，我们传入的arr是变化的，这就代表了我们开辟的L和R同样也是变化的。我们就没办法直接去乘递归深度来得到内存开销了。

这个时候往往需要我们站在宏观的角度去分析问题，我们可以发现对于当前的L和R数组而言，它们拼接起来就是传入的arr。进而可以想到，如果我们画出递归树的话，一整层的L和R都拼接起来，刚好就是完整的数组。