我目前正在阅读《算法简介》这本书，并且我有一个关于分析算法的问题：
根据这本书，归并排序的计算成本是 c lg n，它说
我们将 c 限制为一个常数，这样字长就不会随意增长（如果字长可以任意增长，我们可以在一个字中存储大量数据并在恒定时间内对其进行操作）
我不明白这里“常量”的含义。谁能解释清楚这是什么意思？
问问题
62 次
2 回答
0
算法研究中的计算复杂性涉及找到为算法需要多少时间（或空间）提供上限和下限的函数。回想一下高中的基本代数，在那里你学习了一条线的一般点斜率公式？该公式y = mx + b提供了两个参数，m（斜率）和 b（y 截距），它们完整地描述了一条线。这些常数 (m,b) 描述了线的位置，更大的斜率意味着线更陡峭。
算法复杂度只是描述算法运行时间（和/或需要多少空间）的上限（可能还有下限）的一种方式。使用 big-O（和 big-Theta）表示法，您可以找到一个为算法成本提供上限（和下限）的函数。常数只是移动曲线，而不是改变曲线的形状。
于 2013-10-29T01:48:39.930 回答
0
我们将 c 限制为一个常数，这样字长就不会随意增长（如果字长可以任意增长，我们可以在一个字中存储大量数据并在恒定时间内对其进行操作）
在物理计算机上，机器字有一些最大大小。在 32 位系统上，这将是 32 位，而在 64 位系统上，它可能是 64 位。对机器字的操作（通常）被假定为花费时间 O(1)，即使它们同时对很多位进行操作。例如，如果您对一个机器字使用按位或或按位与，您可以将其视为在单个时间单位内执行 32 或 64 次并行或或与操作。
在尝试为计算系统构建理论模型时，有必要假设机器字的最大大小有一个上限。如果您不这样做，那么您可以声称您可以执行诸如“在 O(1) 时间内计算 n 个值的 OR”或“在 O(1) 时间内将两个任意精度数相加”之类的操作你实际上无法在真正的计算机上做到这一点。因此，通常假设机器字具有某个最大大小，因此如果您确实想要计算 n 个值的 OR，您仍然可以这样做，但您不能通过将所有值打包到一台机器中来立即完成word 并执行一条汇编指令以获得结果。
希望这可以帮助！
于 2013-10-29T15:52:30.213 回答