在这种情况下，“常量”是什么意思？

Question

我目前正在读算法导论书，我有一个问题关于分析的算法：

的合并排序的计算成本是根据书çLG n和它说，

我们将c限制为一个常数，以便字大小不会随意增大（如果字的大小可以任意增长，我们可以将大量数据存储在一个字中，并在一段时间内对其进行操作）

我不明白“常量”的含义。谁能解释清楚这是什么意思？

Answer 1

算法研究中的计算复杂性涉及寻找提供算法需要多少时间（或空间）的上限和下限的函数。回想一下高中的基本代数，你学习了一条线的一般点斜率公式吗？该公式y = mx + b提供了两个参数，m（斜率）和b（y截距），它们完全描述了一条直线。那些常数（m，b）描述了线的位置，而较大的斜率表示线更陡。

算法复杂度只是一种描述算法花费多长时间（和/或需要多少空间）的上限（也可能低于下限）的方法。使用big-O（和big-theta）符号，您可以找到为算法成本提供上限（和下限）的函数。常数只是移动曲线，而不是改变曲线的形状。

Answer 2

我们限制C到是一个常数，使得字的大小不arbirarily增长（如果字的大小可以随意增长，我们可以存储大量的数据在一个字，在固定时间上的所有操作）

在物理计算机上，机器字有一些最大尺寸。在32位系统上，这可能是32位，而在64位系统上，它可能是64位。对机器字的操作（通常）被假定为花费时间O（1），即使它们同时在很多位上操作。例如，如果您在机器字上使用按位或或按位AND，则可以将其视为在一个单位时间内执行32或64个并行OR或AND操作。

当试图建立一个计算系统的理论模型时，有必要假定一个机器字的最大尺寸的上限。如果你不这样做，那么你可以声称你可以执行诸如“在时间O（1）中计算n个值的OR”或者“在时间O（1）中加上两个任意精确数字”的操作，“操作你实际上不能在真正的电脑上做。因此，通常假定机器字有一些最大尺寸，所以如果你想要计算n值的OR，你仍然可以这样做，但是你不能通过将所有值打包到一台机器单词并执行单个汇编指令来获得结果。

希望这会有所帮助！