我正在阅读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 位整数）这在某些情况下可能不合适，或者已经过时。
您至少需要 lg n 位来表示大小为 n 的整数，因此这是存储大小为 n 的输入所需的位数的下限。设置常数 c >= 1 使其成为下限。如果常数乘数小于 1，则您将没有足够的位来存储 n。
这是 RAM 模型中的一个简化步骤。它允许您将每个单独的输入值视为可以在内存的单个插槽（或“单词”）中访问，而不用担心可能出现的并发症。（如果我们使用允许不同字长的模型，加载、存储和复制不同字长的值将花费不同的时间。）这就是“使我们能够索引单个输入元素”的意思。假设问题的每个输入元素都可以在单个地址或索引处访问（意味着它适合一个内存字），从而简化了模型。
这个问题是很久以前提出的，这些解释对我很有帮助，但我觉得关于 lg n 是如何产生的，还有更多的澄清。对我来说，谈论事情真的很有帮助：
让我们选择一个以 10 为底的随机数，比如 27，我们需要 5 位来存储它。为什么？好吧，因为 27 在二进制中是 11011。注意 11011 有 5 个数字，每个“数字”就是我们所说的位，因此是 5 位。
将每一位视为一个插槽。对于二进制，这些插槽中的每一个都可以容纳 0 或 1。我可以用 5 位存储的最大数字是多少？好吧，最大的数字将填满每个插槽：11111
11111 = 31 = 2^5 所以要存储 31 我们需要 5 位，而 31 是 2^5
通常（为了清楚起见，我将使用非常明确的名称）：
numToStore = 2 ^ numBitsNeeded
由于 log 是指数的数学倒数，我们得到： log(numToStore) = numBitsNeeded
由于这可能不会导致整数，因此我们使用 ceil 将我们的答案四舍五入。因此，应用我们的示例来找出存储数字 31 需要多少位：
log(31) = 4.954196310386876 = 5 位