← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 1708.b.3.d · 生成模型:未记录

编码改变查询与维护成本

理解等级:中级

判断整数二进制表示中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的值对数增长。但是,在第