知识卡片
编码改变查询与维护成本
判断整数二进制表示中1的个数奇偶性,直接扫描n位需要检查输入;若编码额外保存可信的奇偶位,查询该位可为O(1),但生成或更新这个附加位也有成本,且必须保证它与原数据一致。
书例15137300128的二进制为1110000110010000001101111010100000,共34位、14个1;附加0表示偶数。原文在这里混用“字节”和位,并前后把直接扫描相对n的增长说成线性又说对数;以n为二进制位数时扫描为O(n),以数值x为变量才约为O(log x)。
03135还用同一俳句的不同文字编码说明表示并非只有一种。原文“64位算法一定比32位花两倍时间”不能由字宽单独推出,实际取决于平台和操作。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
校检位来表示1的数目的奇偶性。 x的编码2:1110000110010000001101111010100000[0] 我们可以看到x的这种编码方式的最后一个位是0,这表示1的个数为偶数个(偶数用0表示)。对于这种表示法,需要35个字节。在两种编码方式中,样本编码的规模都随x的值对数增长。但是,在第
参考来源
- 位置:《算法技术手册》第2章《问题样本的规模》(spine1461;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1425.html;u024-ch02-005)。
- 结论依据:24全文、奇偶位完整示例与03135三种文本表示实读;34位和14个1通过独立整数计数核算,非执行原书程序。
- 原始内容:校检位来表示1的数目的奇偶性。 x的编码2:1110000110010000001101111010100000[0] 我们可以看到x的这种编码方式的最后一个位是0,这表示1的个数为偶数个(偶数用0表示)。对于这种表示法,需要35个字节。在两种编码方式中,样本编码的规模都随x的值对数增长。但是,在第