知识卡片
逐字节扩容成本可累积
固定字母表下统计、构树和按码长读写可按原符号数线性估计,但源码压缩端每新增输出字节调用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