编程语言导论/成本模型导论

编程语言结构可能具有特定的渐进复杂度，程序员应该了解这些复杂度，以便编写高效的算法。换句话说，即使算法具有一些特定的、众所周知的计算成本，其实现也可能具有更高的复杂度，这是由于该语言运行时环境中隐含的成本模型造成的。此外，一些编程语言缺少某些特性，这可能会使高效算法的实现复杂化。例如，在没有桶排序的情况下，很难实现随机访问数据结构。这些细节涉及编程语言实现的一个方面，我们称之为成本模型。

在本章中，我们将探讨四种成本模型。第一个模型与遵循Lisp 模型的编程语言中的列表使用有关。第二个成本模型与支持递归的语言中的函数调用有关。之后，我们将研究Prolog的统一模型，试图分析导致统一效率更高或更低的因素。最后，我们将讨论支持数组的语言，数组是随机访问数据结构。