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(树高)

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

[qw124341789]

作者大大，我有个疑问：2.4.2小节说loop（）函数在循环中调用了n次func（），每轮都返回并释放空间，因此此时的空间复杂度仍然为O（1）；当func（）的

[qw124341789]

当func（）的值被一个int变量a接到了，那空间复杂度是O（n）还是O（1）啊

[qw124341789]

线性阶 O(n)的C语言的代码的malloc（）函数没有强制类型转化，使用的时候应该会发生错误吧

[krahets]

当func（）的值被一个int变量a接到了

你是说把 func() 返回的 int 值赋给变量 a 吗？这个不会影响空间复杂度的，变量 a 占用 O(1) 空间

[qw124341789]

感谢你的回复，解答了我的疑问

[Kakarrot-SunGoku]

这个可视化是真滴棒

[Great-R]

你好我想问一下，空间复杂度的O(n^2)中的c语言的递归实现，每个栈帧都只初始化了一个数组，这样的空间复杂度不应该是线性递增的吗，n个栈，n个数组，不是O(n)的复杂度嘛?

[krahets]

Hi，这 n 个数组的长度分别为 1, 2, ..., n-1, n，平均长度为 n/2 ，因此总体空间复杂度为 O(n/2 * n) = O(n^2)

[Byzhazha]

K神，我对C语言有些强迫症，或者是有点讨厌java的括号风格，所以在写c语言的时候，总会把括号另起一行，正常吗？

[krahets]

Hi，这个没有绝对的对错，编程语言通常有多种代码格式标准，我猜（不确定）一定存在满足你喜好的代码格式标准

[qw457812]

请教一下，调用的函数内的暂存数据占用的空间需要考虑吗？因为我看下一节说栈帧空间通常仅在递归函数中影响空间复杂度，所以有这个疑问

[krahets]

需要考虑，但函数返回后这些空间会被释放掉。

• 在迭代中，每轮函数执行完返回，空间不会产生累积。
• 而在递归中，未返回的的函数会随着“递”的过程不断累积，从而实际影响到空间复杂度。

[qw457812]

明白了，感谢K神

[RuntianLee]

老师好，请问b = [0] * 10000空间复杂度为什么是O(1)而不是O(n)呢？列表中的每个元素不是都占一个空间吗？

[krahets]

新年快乐！因为 b = [0] * 10000 中不包含 n ，或者说 b 占用的空间不受 n 的影响；它虽然很大，但仍是常数级别

[JasonNum1]

你好,图 2-18中所述的空间复杂度为什么不考虑递归所产生的n个函数?麻烦解答下

[krahets]

Hi，递归使用的栈帧空间的空间复杂度是 $O(n)$，比数组使用的 $O(n^2)$ 空间更小，因此可以省略统计。

[JasonNum1]

一语点醒梦中人,感谢!

[guowei-gong]

大O计算的是趋势，而不是具体的次数呀 在 2024年2月18日星期日，Yudong Jin ***@***.***> 写道：

…

Hi，递归使用的栈帧空间的空间复杂度是 $O(n)$，比数组使用的 $O(n^2)$ 空间更小，因此可以省略统计。 — Reply to this email directly, view it on GitHub <#19 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AO42YQBCVJX7QIAPUYGWLZDYUDYURAVCNFSM6AAAAAASLISPNKVHI2DSMVQWIX3LMV43SRDJONRXK43TNFXW4Q3PNVWWK3TUHM4DKMBSGMZDC> . You are receiving this because you commented.Message ID: ***@***.***>

[youxiuqingnianjiushiwo]

K神您好！想问一下，这段代码的任务是什么呀？

int linearLogRecur(float n) {
    if (n <= 1)
        return 1;
    int count = linearLogRecur(n / 2) + linearLogRecur(n / 2);
    for (int i = 0; i < n; i++) {
        count++;
    }
    return count;
}

[xuejiangping]

个人这样理解的，首先每递归一次 n/2，当满足递归推出条件时，递归深度/层级 为 log2(n)。而每一层的for循环中都有：如第一层n1=8，第二层为n2=(n1)/2=4，但是调用了两次，即2 * 4=8，第三次n3=(n2)/2=2,该层一共调用4次，4 * 2=8。所以可以知道每层for循环是n次，一共log2(n)层。即总次数为：n * log2(n),对数换个底后：n * log(n)/log(2) ,分母 log(2)为常数项可以省略，最后得到 n * log(n)

[youxiuqingnianjiushiwo]

哦天哪，感谢你的解答，我明白了！当时没认真理解下面那张图片的意思，谢谢你！

[GoLennLee]

计算给定数字n的一种复杂度

[NgxuAnGMH]

这一章解释的太清楚啦！感觉回过头要常复习。
1、常数阶：常量、变量、对象
2、线性阶：数组、链表、栈、队列
3、平方阶：矩阵、图
4、指数阶：二叉树（满二叉树）
5、对数阶：分治算法

• 最关键可能还是递归？
• 相信等后续学习了数据结构后，对空间复杂度就更好理解了。

[wcywxq]

标记一下

[CarolineeeeeDev]

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

[talent-strive]

n

[CarolineeeeeDev]

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

[talent-strive]

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

[ruihao-yan]

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

[AmyDmy]

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

[krahets]

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

[forMyReason]

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

[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)才是主要的空间消耗。