前言

本篇文章收录于专辑：http://dwz.win/HjK，点击解锁更多数据结构与算法的常识。

你好，我是彤哥，一个每天爬二十六层楼还不忘读源码的硬核男人。

上一节，咱们一起学习了复杂度剖析的套路和常见的复杂度。

然而，咱们的案例根本都是以工夫复杂度为主，很少接触到空间复杂度。

那么，到底什么才是真正的空间复杂度呢？在空间与工夫发生冲突时又该如何衡量呢？

本节，咱们就来解决这两个问题。

来个例子

当初有一个算法是这样的，给定一个数组，将数组中每个元素都乘以 2 返回，我实现了上面两种模式：

private static int[] multi1(int[] array) {int[] newArray = new int[array.length];
    for (int i = 0; i < array.length; i++) {newArray[i] = array[i] * 2;
    }
    return newArray;
}

private static int[] multi2(int[] array) {for (int i = 0; i < array.length; i++) {array[i] = array[i] * 2;
    }
    return array;
}

暂且不管这两个算法孰好孰坏，你来猜猜他们的空间复杂度各是多少？

你可能会说第一个算法的空间复杂度为 O(n)，第二个算法的空间复杂度为 O(1)。

错！两个算法的空间复杂度都是 O(n)。

也不能说你齐全错了，因为大部分书籍或者材料都弄错了。

是时候理解真正的空间复杂度了。

空间复杂度与额定空间复杂度

空间复杂度 ，是指一个算法运行的过程占用的空间，这个空间包含输出参数的占用空间和额定申请的空间。

所以，针对下面两个算法：

• 第一个算法，输出参数 n，额定空间 n，两者相加为 2n，去除常数项，空间复杂度为 O(n)；
• 第二个算法，输出参数 n，额定空间 0，两者相加为 n，空间复杂度为 O(n)。

能够看到，应用空间复杂度很难判断这两个算法的好坏，所以，诞生了另一个概念——额定空间复杂度。

额定空间复杂度 ，是指一个算法运行过程中额定申请的空间。

应用额定空间复杂度，针对下面两个算法：

• 第一个算法，额定空间为 n，额定空间复杂度为 O(n)；
• 第二个算法，额定空间为 0，额定空间复杂度为 O(1)；

仿佛没见过有 O(0) 这种写法。

能够看到，应用额定空间复杂度可能很轻易地判断两个算法的好坏（从空间占用的角度）。

所以，是时候纠正错误的概念了，当前与人交换的时候请应用“额定空间复杂度”这个概念。

工夫与空间的衡量

工夫与空间往往是一组纠缠在一起的概念，就像很多小说中写的一样，配角最终领悟了时空法令，成为了最强者，小说完结。

在数据结构与算法中也是一样，工夫与空间往往同时呈现，而且常常朝着相同的方向静止。

比方，对于排序算法：

• 冒泡排序，工夫复杂度 O(n^2)，空间复杂度 O(1)
• 归并排序，工夫复杂度 O(nlogn)，空间复杂度 O(n)

所以，有两种思维：以工夫换空间，以空间换工夫。

那么，哪种算法更好呢？

我认为，如果有工夫、空间同时比拟小的为最好，退而求其次，我抉择以空间换工夫，毕竟，随着计算机硬件技术地一直倒退，空间越来越不值钱，而工夫却越来越值钱，所以，以空间换工夫也是一种罕用的思维，在咱们后续的课程中会呈现大量以空间换工夫的案例。

想晓得冒泡排序和归并排序算法的复杂度如何计算吗？来呀，关注我吧。

后记

本节，咱们从一个小例子动手，剖析了两种算法的空间复杂度，并引出空间复杂度的真身——额定空间复杂度，最初，通过比照冒泡排序和归并排序的工夫复杂度和空间复杂度，得出了以空间换工夫的思维。

到这里，对于复杂度相干的章节就写完了，从下一节开始，咱们将进入罕用数据结构与算法的学习中，敬请期待。

P.S. 下周将进行降职问难，会停更几天，敬请体谅。

关注公号主“彤哥读源码”，解锁更多源码、根底、架构常识。