c - 在动态数组的摊销分析中考虑 malloc 是否错误？

Question

我在一项家庭作业上扣了一些分数，因为在动态数组的摊销分析中计算了错误的总成本。我认为评分者可能只看总数，而不是我采取的步骤，而且我认为我考虑了 malloc，而他们的答案没有。

这是我的分析的一部分:

我们看到的示例没有考虑到 malloc，但我看到了一个视频，它很有意义，所以我把它放在那里。我意识到虽然 malloc 是一个相对昂贵的操作，但这里可能是 O(1)，所以我可以忽略它。

但我的问题是:进行此类分析时是否只有一种方法来计算成本？是否存在客观的正确和错误成本，或者得出的结论才是真正重要的？

Answer 1

您问:“进行此类分析时是否只有一种方法来计算成本？”答案是否定的。

这些分析是针对机器的数学模型，而不是真实的机器。当我们说“追加到可调整大小的数组是 O(1) 摊销”之类的事情时，我们正在抽象出算法中所需的各种过程的成本。动机是即使你和我拥有不同的机器，也能够比较算法。

但是，除了不同的物理机器之外，还有不同型号的机器。例如，某些模型不允许整数在恒定时间内相乘。某些模型允许变量为无限精度的实数。在某些模型中，所有计算都是免费的，唯一跟踪的成本是从内存中获取数据的延迟。

随着硬件的发展，计算机科学家提出了在算法分析中使用新模型的论据。例如，参见 Tomasz Jurkiewicz 的工作，包括"The Cost of Address Translation" .

听起来您的模型包含了 malloc 的具体成本。这既不错误也不正确。在您的计算机上它可能是一个更准确的模型，而在分级机上它可能是一个不太准确的模型。