程式語言導論/成本模型導論

程式語言構造可能具有特定的漸近複雜度，程式設計師應該瞭解這些複雜度，以產生高效的演算法。換句話說，即使演算法具有某種特定的、眾所周知的計算成本，其實現也可能具有更高的複雜度，因為隱式成本模型是該語言執行時環境的一部分。此外，一些程式語言缺少可能使高效演算法實現變得複雜的功能。例如，如果沒有桶排序，就很難實現隨機訪問資料結構。這些細節涉及我們稱為成本模型的程式語言實現的一個方面。

在本章中，我們將研究四種成本模型。第一個涉及使用遵循Lisp 模型的程式語言中的列表。第二個成本模型涉及在支援遞迴的語言中呼叫函式。之後，我們研究了Prolog 的統一模型，試圖推斷導致統一效率更高或更低的原因。最後，我們討論了支援陣列的語言，陣列是隨機訪問資料結構。