知识卡片

普通读书笔记卡 · 1285.j.1.s · 生成模型:未记录

逐字节扩容成本可累积

理解等级:中级

固定字母表下统计、构树和按码长读写可按原符号数线性估计,但源码压缩端每新增输出字节调用realloc,解压端也每恢复一个字节重新分配。若每次移动并复制已有内容,总搬移量可达1+2+…+n,即二次量级;realloc原地扩展时又可能较便宜。

因此源码O(n)说明忽略了动态分配器的潜在搬移成本,也不是网络耗时上界。预分配合法上限或按容量倍增可降低反复复制,但仍需溢出检查、输入长度验证和正确码树。没有对这些C函数进行运行或性能测试。

270/03042–03043恢复每个短语或字面标记都按当前实际输出长度realloc,没有独立增长容量。标记数可随输入线性增长,累计搬移仍可能二次。03040压缩返回(opos/8)+1,若恰好字节对齐会多报一字节;空输入只有sizeof(int)已分配头部却也多报一字节。书中O(n)和性能比较不能证明当前代码实际长度/分配都正确。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

      O(n),其中n是原始数据中符号的数量。这是因为,对每个要解码符号来说,在霍夫曼树中向下寻找的深度是一个有界常量,这个常量依赖于数据中不同符号的数量。在本节的实现中,这个常量为256。建立霍夫曼树的过程不影响huffman_uncompress的复杂度,因为这个过程只依赖于数据中不同符号的个数。 示

    • · 查看原书依据

      O(n),其中n是原始数据中符号的个数。这是因为,对于编码数据中每n/c个要解码的标记,当执行将滑动窗口中的符号拷贝到恢复缓冲区的固定时间操作时,1/c是一个代表编码效率的常量因素。所以,lz77_uncompress的时间复杂度是O(n).但其过程不受常量因子影响。这就解释了为什么其性能比huff

    参考来源

    - 位置:《算法精解:C语言描述》第14章《huffman_uncompress》(spine1386;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1352.html;u261-ch14-020)。 - 结论依据:260/261复杂度文字与03027逐字节realloc、03029逐恢复字节realloc完整实读。 - 原始内容:O(n),其中n是原始数据中符号的数量。这是因为,对每个要解码符号来说,在霍夫曼树中向下寻找的深度是一个有界常量,这个常量依赖于数据中不同符号的数量。在本节的实现中,这个常量为256。建立霍夫曼树的过程不影响huffman_uncompress的复杂度,因为这个过程只依赖于数据中不同符号的个数。 示 - 位置:《算法精解:C语言描述》第14章《lz77_uncompress》(spine1393;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1359.html;u270-ch14-020)。 - 结论依据:270/03042–03043恢复每个短语或字面标记都按当前实际输出长度realloc,没有独立增长容量。标记数可随输入线性增长,累计搬移仍可能二次。03040压缩返回(opos/8)+1,若恰好字节对齐会多报一字节;空输入只有sizeof(int)已分配头部却也多报一字节。书中O(n)和性能比较不能证明当前代码实际长度/分配都正确。 - 原始内容:O(n),其中n是原始数据中符号的个数。这是因为,对于编码数据中每n/c个要解码的标记,当执行将滑动窗口中的符号拷贝到恢复缓冲区的固定时间操作时,1/c是一个代表编码效率的常量因素。所以,lz77_uncompress的时间复杂度是O(n).但其过程不受常量因子影响。这就解释了为什么其性能比huff