Gee*_*eek 11 algorithm integer
我正在阅读Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein的"算法导论 "一书.在"分析算法"的第二章中,提到:
我们还假设对每个数据字的大小进行限制.例如,当使用大小为n的输入时,我们通常假设整数由c lg n位表示,对于某些常数c> = 1.我们要求c> = 1,这样每个单词都可以保存n的值,使我们能够索引各个输入元素,并且我们将c限制为常量,这样单词大小就不会随意增长.(如果单词大小可以任意增长,我们可以在一个单词中存储大量数据,并在恒定时间内对其进行操作 - 显然是不切实际的情况.)
我的问题是为什么这个假设每个整数应该由c lg n位表示,以及c> = 1的情况如何允许我们索引各个输入元素？
首先,lg它们显然意味着日志基数2,所以lg n是位数n.
那么他们所说的是,如果他们有一个算法来获取一个数字列表(我在我的例子中更具体,以帮助使其更容易理解),1,2,3,...n那么他们认为:
记忆中的"单词"足以容纳任何这些数字.
内存中的"单词"不足以容纳所有数字(在一个单词中,以某种方式打包).
当计算算法中"步数"的数量时,对一个"单词"的操作需要一步.
他们这样做的原因是为了保持分析的真实性(你只能在"原生"类型中存储一些大小的数字;之后你需要切换到任意精度库)而不选择特定的例子(如32位整数)在某些情况下可能不合适或过时.