算法分析——大O标记法之空间复杂度

女爷i 2024-04-08 08:28 56阅读 0赞

> 大家可移步[算法分析——大O标记法][O]进行对大O标记法进行了解；

--------------------

**目录**

一. 理解空间复杂度

二. 空间复杂度 O(1)

三. 空间复杂度 O(n)

--------------------

## 一. 理解空间复杂度 ##

> 既然时间复杂度不是用来计算程序具体耗时的，那么我也应该明白，空间复杂度也不是用来计算程序实际占用的空间的。

> 空间复杂度(SpaceComplexity)是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，我们用S(n) 来定义，关心算法需要的额外空间。

> 在电子计算机时代的早期，时间和空间这两种资源都是极其昂贵的。但是经过几十年不懈的技术革新，计算机的速度和存储容量已经提高了好几个数量级。现在，一个算法所需要的额外空间，往往已经不是我们关注的重点问题了。因此现阶段算法重点关注的是时间复杂度，也就是上一节的内容。

> 空间复杂度比较常用的有：O(1)、O(n)，

--------------------

## 二. 空间复杂度 O(1) ##

> 如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)

**举例：**

int i = 1;
    int j = 2;
    ++i;
    j++;
    int m = i + j;

> 代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)。

--------------------

## 三. 空间复杂度 O(n) ##

> 我们先看一个代码：

int[] m = new int[10];
    int j;
    for(int i=1; i<=m.length; ++i){
        j = i;
        j++;
    }

> 这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)

[O]: https://blog.csdn.net/weixin_53919192/article/details/126329470?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22126329470%22%2C%22source%22%3A%22weixin_53919192%22%7D

发表评论取消回复

表情：

评论列表（有 0 条评论，56人围观）

还没有评论，来说两句吧...

相关阅读

相关算法分析——大O标记法之空间复杂度

> 大家可移步[算法分析——大O标记法][O]进行对大O标记法进行了解； -------------------- 目录一. 理解空间复杂度二. 空间复杂度 O(1

女爷i/ 2024年04月08日 08:28/ 0 赞/ 57 阅读

相关算法分析——大O标记法之时间复杂度

> 大家可移步[算法分析——大O标记法][O]进行对大O标记法进行了解； -------------------- 目录一. 理解不同的大O 运行时间算法1 算法

た入场券/ 2024年04月08日 08:25/ 0 赞/ 82 阅读

相关算法分析——大O标记法

目录一. 运行时间二. 大O 表示法 2.1 示例三. 总结五. 扩展 -------------------- 一. 运行时间 > 每次介绍算法

悠悠/ 2024年04月08日 08:25/ 0 赞/ 75 阅读

相关算法的时间复杂度分析之O(logn)、O(nlogn)

复杂度分析之O(logn)、O(nlogn) 对数阶时间复杂度非常常见，同时也是最难分析的一种时间复杂度。我通过一个例子来说明一下。 int i = 1;

浅浅的花香味﹌/ 2022年12月15日 11:29/ 0 赞/ 154 阅读

相关时间复杂度/空间复杂度O(1)、O(n)

1.名词解析 O(x):表示算法时空（时间/空间）的复杂度 O括号里的函数 x 表示：某个算法的耗时/耗空间与数据增长量之间的关系。其中O(n),O(n^2)等的

妖狐艹你老母/ 2022年12月04日 09:10/ 0 赞/ 177 阅读

相关算法的时间复杂度表示法(大O表示法)

大 O 复杂度表示法算法的执行效率，粗略地讲，就是算法代码执行的时间。但是，如何在不运行代码的情况下，用“肉眼”得到一段代码的执行时间呢？ for a in

今天药忘吃喽~/ 2022年11月21日 01:06/ 0 赞/ 216 阅读

相关「算法」时间、空间复杂度分析

1. 衡量算法性能的标准数据结构和算法本身解决的是“快”和“省”的问题，即如何让代码运行得更快，如何让代码更省存储空间。所以，执行效率是算法一个非常重要的考量指标。那如

喜欢ヅ旅行/ 2022年11月06日 03:54/ 0 赞/ 259 阅读

相关算法分析（时间复杂度和空间复杂度）

算法分析（时间复杂度和空间复杂度）对于一个给定的算法需要做两项分析，第一就是证明算法的正确性，第二就是计算算法的复杂度。算法的复杂度包括时间复杂度和空间复杂度。 1

梦里梦外;/ 2022年04月22日 14:24/ 0 赞/ 276 阅读

相关算法复杂度和大O表示法

概念算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。时间复杂度一个算法执行所耗费的时间，从理论上是不能算出来的，必须

我不是女神ヾ/ 2021年09月20日 11:20/ 0 赞/ 276 阅读

相关排序算法之时间复杂度、空间复杂度

<table> <thead> <tr> <th>排序算法</th> <th>最好时间</th> <th>平均时间</th> <th>

￡神魔★判官ぃ/ 2021年09月18日 04:22/ 0 赞/ 548 阅读