那么一直还没有讲空间复杂度,所以打算陆续来补上,内容不难,大家可以读一遍文章就有整体的了解了。
什么是空间复杂度呢?
是对一个算法在运行过程中占用内存空间大小的量度,记做S(n)=O(f(n)。
空间复杂度(Space Complexity)记作S(n) 依然使用大O来表示。利用程序的空间复杂度,可以对程序运行中需要多少内存有个预先估计。
关注空间复杂度有两个常见的相关问题
- 空间复杂度是考虑程序(可执行文件)的大小么?
很多同学都会混淆程序运行时内存大小和程序本身的大小。这里强调一下空间复杂度是考虑程序运行时占用内存的大小,而不是可执行文件的大小。
- 空间复杂度是准确算出程序运行时所占用的内存么?
不要以为空间复杂度就已经精准的掌握了程序的内存使用大小,很多因素会影响程序真正内存使用大小,例如编译器的内存对齐,编程语言容器的底层实现等等这些都会影响到程序内存的开销。
所以空间复杂度是预先大体评估程序内存使用的大小。
说到空间复杂度,我想同学们在OJ(online judge)上应该遇到过这种错误,就是超出内存限制,一般OJ对程序运行时的所消耗的内存都有一个限制。
为了避免内存超出限制,这也需要我们对算法占用多大的内存有一个大体的预估。
同样在工程实践中,计算机的内存空间也不是无限的,需要工程师对软件运行时所使用的内存有一个大体评估,这都需要用到算法空间复杂度的分析。
来看一下例子,什么时候的空间复杂度是
int j = 0;
for (int i = 0; i < n; i++) {
j++;
}
第一段代码可以看出,随着n的变化,所需开辟的内存空间并不会随着n的变化而变化。即此算法空间复杂度为一个常量,所以表示为大O(1)。
什么时候的空间复杂度是O(n)?
当消耗空间和输入参数n保持线性增长,这样的空间复杂度为O(n),来看一下这段C++代码
int* a = new int(n);
for (int i = 0; i < n; i++) {
a[i] = i;
}
我们定义了一个数组出来,这个数组占用的大小为n,虽然有一个for循环,但没有再分配新的空间,因此,这段代码的空间复杂度主要看第一行即可,随着n的增大,开辟的内存大小呈线性增长,即 O(n)。
其他的 O(n^2), O(n^3) 我想大家应该都可以以此例举出来了,那么思考一下 什么时候空间复杂度是 O(logn)呢?
空间复杂度是logn的情况确实有些特殊,其实是在递归的时候,会出现空间复杂度为logn的情况。
至于如何求递归的空间复杂度,我会在专门写一篇文章来介绍的,敬请期待!