隨機存取機器模型（RAM model）

隨機存取機器模型，是我們說某演算法要花「n 步」時，暗中想像的那台理想電腦。真實機器複雜得令人眼花——快取、管線、變動的時脈——若我們在某台特定筆電上數奈秒，分析放到別台就毫無用處。於是我們改而約定一台簡單、虛構卻合理的機器，在它上面數操作，得到一個乾淨、與機器無關的成本衡量。RAM 是 random-access machine（隨機存取機器）的縮寫：「隨機存取」意指你能一步直達任何記憶體格，就像你能憑頁碼直接翻到書的任一頁，而不必一頁一頁翻。

在這個模型裡，記憶體是一個無界的格子陣列，每格存一個字組（一個適合此機器、大到足以為輸入編索引的數）。基本操作——讀或寫一格、加、減、乘、比較、跟隨一個分支——每個都花一單位時間。所以要衡量演算法的執行時間，我們只需把它執行的這類操作數，表示成輸入規模 n 的函數來計。走一遍 n 個項目的清單找最大值，約做 n 次比較加上一點記帳工作，所以我們稱它為線性、約 n 步。這個模型刻意忽略快機與慢機之間的常數差異，因為那些只是把一切乘上一個固定倍數，並不改變工作量隨 n 成長的方式。

隨機存取機器模型是一種簡化，值得知道它在哪裡會失真。它「一個字組、單位成本」的假設，只在所涉數值能舒適地塞進一個機器字組時才公平；把上千位數的整數相乘其實不是一步，而更講究的位元成本模型會按位數收費。它也假裝每次記憶體存取成本相同，而真實快取讓鄰近的存取便宜得多——這正是為什麼兩個 RAM 步數相同的演算法，真實速度可能不同。儘管如此，對絕大多數分析而言，隨機存取機器模型正是恰當的高度：細到有意義，又抽象到可移植。