知识卡片

普通读书笔记卡 · 5654.c.3.c

空间分析关注同时存活峰值

理解等级:中级

空间成本要先声明统计口径:输入、辅助状态和输出是否计入,再看执行期间最多有多少数据同时需要保留。递归栈、临时容器和结果集合都可能贡献峰值。

逐次创建后不再需要的对象不应简单累计为同时占用;但作用域结束也不保证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 === /*