algorithm - 在分析计算机算法时理解关于机器字长的假设

Question

我正在看书Introduction to Algorithms作者:Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein。在“分析算法”下的第二章中提到:

We also assume a limit on the size of each word of data. For example , when working with inputs of size n , we typically assume that integers are represented by c lg n bits for some constant c>=1 . We require c>=1 so that each word can hold the value of n , enabling us to index the individual input elements , and we restrict c to be a constant so that the word size doesn't grow arbitrarily .( If the word size could grow arbitrarily , we could store huge amounts of data in one word and operate on it all in constant time - clearly an unrealistic scenario.)

我的问题是为什么每个整数都应该由 c lg n 位表示的假设以及 c>=1 的情况如何允许我们索引各个输入元素？

Answer 1

首先，lg 显然是指以 2 为底的对数，因此 lg n 是 n 中的位数。

然后他们说的是，如果他们有一个算法采用数字列表(我在我的示例中更具体以帮助使其更容易理解)，如 1,2,3,.. .n 然后他们假设:

• 内存中的一个“字”足以容纳这些数字中的任何一个。

• 内存中的一个“单词”不足以容纳所有 数字(在一个单词中，以某种方式打包)。

• 在计算算法中的“步数”时，对一个“词”的操作需要一步。

他们这样做的原因是为了保持分析的真实性(你只能在“本地”类型中存储一定大小的数字；之后你需要切换到任意精度的库)而不选择特定的例子(比如 32位整数)在某些情况下可能不合适，或者变得过时。