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

编程语言构造可能具有特定的渐近复杂度，程序员应该了解这些复杂度，以产生高效的算法。换句话说，即使算法具有某种特定的、众所周知的计算成本，其实现也可能具有更高的复杂度，因为隐式成本模型是该语言运行时环境的一部分。此外，一些编程语言缺少可能使高效算法实现变得复杂的功能。例如，如果没有桶排序，就很难实现随机访问数据结构。这些细节涉及我们称为成本模型的编程语言实现的一个方面。

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