chapter_computational_complexity/space_complexity/

[giscus[bot]]

chapter_computational_complexity/space_complexity/

动画图解、一键运行的数据结构与算法教程

https://www.hello-algo.com/chapter_computational_complexity/space_complexity/

[catch6]

【Fig. 空间复杂度的常见类型】图片曲线画的不对，可以找找相关的函数图线工具，目前的曲线有一定的误导，比如如果知道数据量为n<8的情况下选择哪种时间复杂度更合适？按照图线会得出一个错误结论。

[krahets]

哈喽，感谢反馈！您提到本文的 figure ，每个曲线都包含一个常数项，用来把所有曲线的取值范围压缩到一个舒适的范围内。在复杂度（增长趋势）的含义上，它们都是对的。
实际中，因为我们并不知道每个方法的“常数项”复杂度是多少，所以一般无法仅凭复杂度来选择 n = 8 之下的最优解法；但相对地 n = 8e5 就很好选了，这是复杂度占主导的情况。复杂度体现的是增长趋势，而不是绝对的大小～

[guowei-gong]

在第一个示例的 Go 示例中，注释中提到 函数（或称方法） ，我认为不是特别严谨。不能混淆它们的概念。
在 Go 中的函数往往是指：

func funcName() {}

方法是指：

func (s *this) methodName() {}

[krahets]

感谢指出！我再来补充解释下两个术语的区别：

• 函数（function）可以独立被执行，所有参数都以显式传递。
• 方法（method）与一个对象关联，方法被隐式传递给调用它的对象，方法能够对类的实例中包含的数据进行操作。

[iGao101]

有个疑问

/* 递归 O(n) */
void recur(int n) {
    if (n == 1) return;
    return recur(n - 1);
}

这段代码不是尾递归吗？

[krahets]

很细致！是的，这是尾递归，理论上可以将空间复杂度优化至 $O(1)$ 。不过绝大多数编程语言（例如 Java, Python, C++, Go, C# 等）都不支持自动优化尾递归，因此在这里写 $O(n)$

[fallenleavesguy]

空间复杂度和时间复杂度内容比较像，所以这章细节不如上一章多。感谢K神

[krahets]

对的，有些地方是共通的～

[zhuasdfg]

打卡，二叉树的例子不是很懂，等学完再回来

[08822407d]

我的直觉告诉我递归遍历二叉树的空间复杂度应该是远小于O(2^(n - 1))，考虑递归调用过程，只有每进入树的下一层的时候，才会增加一个栈帧，而每当返回上一层的时候就会立即销毁一个栈帧，即是说栈帧数量与递归深度成正比，如果递归代码里没有只malloc()而不free()的行为，那空间复杂度应该是O(n)。用图解的方式说，从根节点画一条线到当前递归代码所在节点，只有在线上的节点才创建了栈帧，不在线上的节点要么栈帧已经无效，要么还没创建栈帧。

[Joeljt]

可是空间复杂度计算的本来不就是函数执行过程中的内存占用吗？如果按你这么说的话，那递归方法也是不存在一个中间状态的，要么已经执行过返回了，要么还没执行，执行到最后一层的内存占用应该是 O(1)，因为栈里边的函数都执行完返回了，所以没有内存占用，但是这好像不太对劲吧

[08822407d]

我最后一句不是说的很清楚么，不在递归路线上的节点才只有“已执行“和”未执行”两种状态，只有在递归路线上的节点才是真正占用栈空间的节点。

[WangBenpeng]

如果我直接调用root.left.left.left.left...(n个)...left，按照楼主的说法我每次调用的时候直接把上一级的节点丢掉吗？肯定是都存储好了的，所以每个节点都要占用内存的

[chestNutLsj]

你把题目改了，作者原书中提到空间复杂度考虑的是暂存空间+输出空间，（忽略指令空间），在这个意义下二叉树要存下来就要O(节点数)，但是注意原文提到二叉树的高度是n，而不是总节点数为n，因此此时存储空间就是O(2^(n-1))。至于你提到的遍历空间是没问题的，确实是O(树高)

[zengfantaoGit]

以算法运行中的峰值内存为准，一整颗递归树不同时刻的所占内存不同，最差时刻就是整颗树的深度

[carrot-butcher]

def build_tree(n):
"""指数阶（建立满二叉树）"""
if n == 0:
return None
root = TreeNode(0)
root.left = build_tree(n - 1)
root.right = build_tree(n - 1)
return root
build_tree(2)
AttributeError: 'NoneType' object has no attribute 'left'
作者你好，我再anaconda的jupyter notebook中重新打了一遍关于二叉树的代码，但是总是报错，我和您的代码对了几遍，还是报错，能帮我看下是怎么回事吗？（同样的代码在spider中可以运行，这是为什么啊？）

[krahets]

应该是 TreeNode 类没有被正常初始化，建议用 VSCode 直接运行源码哦

[carrot-butcher]

感谢提醒，我后面在源代码后面又补充了关于TreeNode类的定义，这下应该是正常运行了。
输入：build_tree(2)
输出的结果为：<main.TreeNode at 0x1acf5f73610>

[buynonsense]

2.4.3这里讲了5种空间复杂度类型，图2-6列出了从低到高的次序，可是下面为什么没有按照这个次序，讲完了指数类型又讲到对数类型呢

[krahets]

按照由易到难讲的，理解指数阶之后再理解对数阶会相对容易一些

[clearwater753]

python二叉树报错的，可以尝试补一下TreeNode类的定义：

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

[krahets]

@yesanshao007 用的是仓库的代码嘛？每个代码文件里应该已经正确地引入了 system path 了

[yesanshao007]

用的确实是仓库的代码

[krahets]

@yesanshao007 我用 pycharm 试了一下，可以运行呀。直接用 pycharm 打开 hello-algo 根目录，然后打开 Python 代码直接运行。

[yesanshao007]

那我自己再研究一下，谢谢你😊

[yesanshao007]

特意过来反馈一下，直接用 pycharm 打开 hello-algo 根目录然后直接运行是可以的，不用管代码检查的红色波浪线

[DarKnightL]

常见的几个类型的英文翻译（GPT4 生成）：

1. 常数阶 (O(1)) - Constant Time: An algorithm is said to run in constant time if it requires the same amount of time regardless of the input size. Examples can include accessing an array element by index or inserting a node in a linked list.

2. 线性阶 (O(n)) - Linear Time: An algorithm is considered to have linear time complexity when the time to complete operations increases linearly with the number of inputs. This is seen in scenarios like iterating through each element in a list (e.g., using a for loop to scan an array).

3. 平方阶 (O(n^2)) - Quadratic Time: Quadratic time complexity occurs when the time it takes to execute an algorithm is proportional to the square of the input size. This is commonly experienced in algorithms that involve nested iterations over the data set, such as certain simplistic sorting algorithms like bubble sort or insertion sort.

4. 指数阶 (O(2^n)) - Exponential Time: Exponential time complexity describes an algorithm that doubles in running time with each additional element in the input data set. These algorithms can become impractical very quickly as the size of the input increases. Examples of this complexity often involve algorithms that solve problems through brute force or recursive computations, like many complex number-theoretic algorithms or the naive solution for the Travelling Salesman Problem.

5. 对数阶 (O(\log n)) - Logarithmic Time: Logarithmic time complexity is seen in algorithms that cut the problem in half (or a fraction) with each step. These algorithms are quite efficient as they can handle very large input sizes relatively quickly. Binary search algorithms, for example, exhibit logarithmic time complexity as they divide the searchable elements in half with each step.

[Mars-Boys]

归并排序的空间复杂度为什么是O（logn）啊，不是每个节点递归都要分配栈帧，为什么等于树高

[krahets]

每当函数返回后，系统就会释放它占用的栈帧空间。因此在递归函数中，空间复杂度是由某时刻下“累计未返回的函数的数量”决定的。当输入数据长度为 n 时，归并排序的树高为 log n ，这个树高就是“累计未返回的函数的数量”。

[liplushe]

发现右侧的目录，latex公式没有生效

[krahets]

确实，这是一个尚未解决的bug

[RubuJam]

想请问一下作者，为什么这里是O(n)

if (n > 10) int nums[n] = {0};   // O(n)

[krahets]

Hi，这里初始化了一个长度为 n 的数组，因此空间复杂度为 O(n)

[liangguitao]

Day 5

[ZuoRight]

而与时间复杂度不同的是，我们通常只关注最差空间复杂度。

上一讲说平均时间复杂度不好计算，时间复杂度实际取的是渐近上界，即最差时间复杂度，所以和空间复杂度不是一样么？都是最差。我理解错了？

[krahets]

Hi，平均时间复杂度是很有意义的（最能反映算法效率的优劣）。它考虑的是所有可能的输入情况，以及它们出现的概率，计算出算法在所有这些情况下的期望运行时间。这通常需要假设输入的分布是均匀的，或者至少知道输入的概率分布。由于计算平均时间复杂度通常比较困难，所以在很多情况下，我们主要关注最坏时间复杂度。
对于空间复杂度，我们通常只考虑最差情况。

[CarolineeeeeDev]

想问一问用递归方法求解斐波那契数列的空间复杂度是多少呢？

[talent-strive]

n

[CarolineeeeeDev]

那为什么这上面二叉树的空间复杂度就指数阶呀

[talent-strive]

因为每次二叉树都会一分为二，每次都会多一倍的可能性。比如2，4，8，16。递归方法求解斐波那契数列，就类似一次函数。

[ruihao-yan]

斐波那契那个树不是完整的树吧 a bushy tree

[183Gi]

斐波那契数列本质是一个一维数组，求解时可能用树的形式展示方便理解，但是其实没有那么多数据存储，都是使用的同一个存储空间的数据，所以是O(n)。不知道说的对不对

[matthewdmy]

在“如图 2-18 所示”那段话中，后面说平均长度是n/2是不是说错了 应该是n(n+1)/2

[krahets]

没问题，数组的平均长度是 n/2

[forMyReason]

应该是(n+1)/2吧？

[183Gi]

可以看成一个元素个数为1、2、3.....n-1、n的一个等差数列

[yyeerr]

对数阶那里，归并排序的空间复杂度是O(n)吧？因为每一层在向上归的时候都把临时申请的空间释放了，最大也不超过n

[krahets]

这里讨论的是递归使用的栈帧空间，为 O(log n) ；辅助数组使用 O(n) 空间

[ralphjzhang]

2.4.1, 2.4.2 的 zig 代码是空白啊

[tsingfenger]

2-19，虽然递归调用栈的深度是 O(n)，但是创建的节点数量O(n^2)才是主要的空间消耗。

[zengfantaoGit]

错误的，因为这些节点并不会在同一时刻都会占用内存。只有从根节点的路径节点才会同时占用，不同路径的节点可能运行完后直接释放空间。

[sharrk7mi]

感觉空间复杂度还是不太理解，先看看后续再回顾一下

[Aka-Edward]

有点懵懵的😳。后面再回来看看

[jiuerya7]

我也

[anlan6]

图2-18平方阶运算时不考虑栈帧空间n吗，是因为考虑最差才省去的吧

[playboyzhang]

还是得反复看和练习

[Kruogu]

抓个虫，2.4.3中线性阶的代码注释，是链表不是列表吗？

[yuanjcca]

int function() {
// 执行某些操作
return 0;
}
/* 循环的空间复杂度为 O(1) /
void loop(int n) {
for (int i = 0; i < n; i++) {
function();
}
}
/ 递归的空间复杂度为 O(n) */
void recur(int n) {
if (n == 1) return;
return recur(n - 1);
}
java void可以写return吗？ return recur(n - 1);这句话怎么理解

[183Gi]

这里就是一个尾递归调用，可以看看2.2节。至于void能不能写return，应该是没问题的，因为return是作为一个函数的结束标志，我刚刚学c的时候经常写返回值是void然后还写return 0，但是在java中好像是只能有return关键字，不能写return 0之类的。

[radon000000001]

请问在2-17中所代表的递归代码可以被认为是尾递归吗，从而在某些情况下空间复杂度可以为O(1)?

[183Gi]

我也觉得在支持尾递归的语言中，这里算是空间复杂度是O(1)

[183Gi]

不对，看错了2-17的递归时，每一层的函数执行完毕都没有返回，要到n===1才开始归，在此之前会保存n个调用函数的帧栈，不能算O(1)。2.4.2中对递归的空间复杂度展示才算是尾递归。

[5myth5]

可以看下2.5小结的Q&A，有解释

[Lpf-357]

不是很懂诶

[zq80]

self.next: Node | None = None # 指向下一节点的引用
上面这句python代码没看懂，写到运行python3.9的pycharm中也报错

[jidaojiuyou]

换成

class Node:
    """类"""
    def __init__(self, x: int):
        self.val: int = x              # 节点值
        self.next: "Node" | None = None  # 指向下一节点的引用

你可以理解成手链。手链未合并成圆形之前，你把任意一头抓起来开始编号。每个环（Node）都有编号（val）,同时下一个环（next）也可能是环（Node）也可能没有（None，手链的最后一环后面没有东西了)。

[Ivy129]

1.说完时间复杂度，我们需要在空间复杂度上面去陈述一个算法

在分析一段程序的空间复杂度时，我们通常统计暂存数据、栈帧空间和输出数据三部分
暂存数据：用于保存算法运行过程中的各种常量、变量、对象等。
栈帧空间：用于保存调用函数的上下文数据。系统在每次调用函数时都会在栈顶部创建一个栈帧，函数返回后，栈帧空间会被释放。
指令空间：用于保存编译后的程序指令，在实际统计中通常忽略不计。

其中需要额外注意一下的是：栈帧空间。
这个概念之前没有接触过。

常量一般用大写。

栈帧空间是：调用函数

2.计算空间复杂度
空间复杂度的推算方法与时间复杂度大致相同，只需将统计对象从“操作数量”转为“使用空间大小”。

而与时间复杂度不同的是，我们通常只关注最差空间复杂度。（这个不同点是需要注意的。）

3.常见类型的空间复杂度
需要注意的是，在循环中初始化变量或调用函数而占用的内存，在进入下一循环后就会被释放，因此不会累积占用空间，空间复杂度仍为 O(1) ：

递归函数产生的线性阶空间复杂度：线性阶

指数阶常见于二叉树。

对数阶常见于分治算法。

4.权衡
降低时间复杂度通常需要以提升空间复杂度为代价，反之亦然。我们将牺牲内存空间来提升算法运行速度的思路称为“以空间换时间”；反之，则称为“以时间换空间”。

选择哪种思路取决于我们更看重哪个方面。在大多数情况下，时间比空间更宝贵，因此“以空间换时间”通常是更常用的策略。当然，在数据量很大的情况下，控制空间复杂度也非常重要。