前言
本篇文章收录于专辑: 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. 下周将进行晋升答辩, 会停更几天, 敬请谅解.
关注公号主 "彤哥读源码", 解锁更多源码, 基础, 架构知识.
来源: https://www.cnblogs.com/tong-yuan/p/13382447.html