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

栏目: IT技术 · 发布时间: 4年前

内容简介:本篇文章收录于专辑:你好,我是彤哥,一个每天爬二十六层楼还不忘读源码的硬核男人。

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

前言

本篇文章收录于专辑: 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. 下周将进行晋升答辩,会停更几天,敬请谅解。

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


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

The Haskell School of Music

The Haskell School of Music

Paul Hudak、Donya Quick / Cambridge University Press / 2018-10-4 / GBP 42.99

This book teaches functional programming through creative applications in music and sound synthesis. Readers will learn the Haskell programming language and explore numerous ways to create music and d......一起来看看 《The Haskell School of Music》 这本书的介绍吧!

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

html转js在线工具
html转js在线工具

html转js在线工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换