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

Question

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

以下是我分析的一部分：

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

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

Answer 1

您问：“在进行此类分析时，是否只有一种方法可以计算成本？” 答案是不。

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

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

随着硬件的发展，计算机科学家为用于算法分析的新模型提出了论据。例如，参见Tomasz Jurkiewicz的作品，包括“地址翻译的成本”。

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