关于java:到底什么才是真正的空间复杂度

本篇文章收录于专辑：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. 下周将进行降职问难，会停更几天，敬请体谅。

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

关于java:到底什么才是真正的空间复杂度

前言

来个例子

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

工夫与空间的衡量

后记