专栏首页彤哥读源码到底什么才是真正的空间复杂度?

到底什么才是真正的空间复杂度?

关注公众号“彤哥读源码”,解锁更多源码、基础、架构知识!

前言

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

上一节,我们一起学习了复杂度分析的套路和常见的复杂度。

但是,我们的案例基本都是以时间复杂度为主,很少接触到空间复杂度。

那么,到底什么才是真正的空间复杂度呢?在空间与时间发生冲突时又该如何权衡呢?

本节,我们就来解决这两个问题。

来个例子

现在有一个算法是这样的,给定一个数组,将数组中每个元素都乘以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. 下周将进行晋升答辩,会停更几天,敬请谅解。

本文分享自微信公众号 - 彤哥读源码(gh_63d1b83b9e01),作者:丹卿

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 复杂度分析的套路及常见的复杂度

    上一节,我们一起学习了表示复杂度的几个符号,我们说,通常使用大O来表示算法的复杂度,不仅合理,而且书写方便。

    彤哥
  • 什么情况下不能使用最坏情况评估算法的复杂度?

    上一节,我们从最坏、平均、最好三种情况分析了算法的复杂度,得出结论,通常来说,使用最坏情况来评估算法的复杂度完全够用了。

    彤哥
  • 4. 死磕 k8s系列之安装包管理工具(Helm)

    Helm可以看作是k8s集群的包管理工具,通过Helm可以快速安装很多软件,比如mysql,nginx等,当然,也可以把自己的应用交给Helm来管理和安装。

    彤哥
  • 算法复杂度(二)

    [ 来自360百科 ]算法在编写成可执行程序后,运行时所需要的资源,资源包括时间资源和内存资源。应用于数学和计算机导论。同一问题可用不同算法解决,而一个算法的质...

    花狗Fdog
  • Python黑帽子-实现netcat基本功能(改进版)

    一个好的渗透测试人员,应该拥有强大的编程能力,而python就是一个很好的工具,我最近也在研究如何用python开发属于自己的小工具,《python黑帽子》是一...

    tnt阿信
  • 解决 Race II 在 Mac 休眠下无法唤醒问题

    2013年的时候,和同事一起买了第一把机械键盘,青轴(还没有被打死),最近配合 Mac 使用,发现有个问题:Mac 休眠后,再打开 Mac 无法...

    前端黑板报
  • Spring Boot程序正确停止的姿势

    基于管理端口方式实现进程关闭实际上是模块spring-boot-actuator提供的功能。

    2Simple
  • PHP中通过getopt解析GNU C风格命令行选项

    在 PHP 中,当我们在获取命令行参数时,可以通过遍历$argv来获取,其实呢是有规范可循的,也就是 GNU C-style parser for comman...

    砸漏
  • 快速驶来的智能出行交通工具,未来去哪?

      这几日全球消费电子领域最大的展会CES在美国拉斯韦加斯正如火如荼地进行。据报道,今年展会共有4119家参展商,其中有1300多家来自中国,接近1/3,为历年...

    曾响铃
  • 如何只用 30 行代码在 JavaScript 中创建一个神经网络

    在这篇文章,我将会展示给你如何使用 Synaptic.js 创建并训练一个神经网络,它允许你在 Node.js 和浏览器中进行深度学习。

    疯狂的技术宅

扫码关注云+社区

领取腾讯云代金券