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

程式語言結構可能具有特定的漸進複雜度，程式設計師應該瞭解這些複雜度，以便編寫高效的演算法。換句話說，即使演算法具有一些特定的、眾所周知的計算成本，其實現也可能具有更高的複雜度，這是由於該語言執行時環境中隱含的成本模型造成的。此外，一些程式語言缺少某些特性，這可能會使高效演算法的實現複雜化。例如，在沒有桶排序的情況下，很難實現隨機訪問資料結構。這些細節涉及程式語言實現的一個方面，我們稱之為成本模型。

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