知识卡片
空间分析关注同时存活峰值
空间成本要先声明统计口径:输入、辅助状态和输出是否计入,再看执行期间最多有多少数据同时需要保留。递归栈、临时容器和结果集合都可能贡献峰值。
逐次创建后不再需要的对象不应简单累计为同时占用;但作用域结束也不保证Go立即把物理内存还给系统。教学逻辑空间、实际GC堆占用和进程常驻内存是不同测量。原书内层nums短声明遮蔽且未使用的示例也不能原样当可编译Go程序。
后续空间例中,线性深度栈、矩阵、完整二叉树分别展示不同增长。spaceQuadraticRecur的数组在递归前已最后使用,真实Go实现可提前认定不再存活,不能无条件把所有层数组相加当实测峰值。归并的对数栈也不等于含辅助数组的总空间为对数;数字转字符串还须说明规模按数值还是位数计。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 2 处
- · 查看原书依据
一般情况下,空间复杂度的统计范围是“暂存空间”加上“输出空间” 。 暂存空间可以进一步划分为三个部分。 ‧ 暂存数据 :用于保存算法运行过程中的各种常量、变量、对象等。 ‧ 栈帧空间 :用于保存调用函数的上下文数据。系统
- · 查看原书依据
如图2‑18 所示,该函数的递归深度为 ,在每个递归函数中都初始化了一个数组,长度分别为 、 、 、 ,平均长度为 ,因此总体占用 空间: // === File: space_complexity.go === /*
参考来源
- 位置:《Hello 算法--Go版本》第02章《复杂度分析》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/1.html;spine 0,归一字符[32895,33005))
- 结论依据:原文输入/暂存/输出及后续峰值两层含义,保留口径差异不将输出忽略为统一规则。
- 原始内容:一般情况下,空间复杂度的统计范围是“暂存空间”加上“输出空间” 。 暂存空间可以进一步划分为三个部分。 ‧ 暂存数据 :用于保存算法运行过程中的各种常量、变量、对象等。 ‧ 栈帧空间 :用于保存调用函数的上下文数据。系统
补充原书证据:spine 1 / extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/2.html;归一字符[1306,1415)。
- 结论依据:实际后续空间图与代码补充峰值的存活和统计口径。
- 原始内容:如图2‑18 所示,该函数的递归深度为 ,在每个递归函数中都初始化了一个数组,长度分别为 、 、 、 ,平均长度为 ,因此总体占用 空间: // === File: space_complexity.go === /*