與機器無關的成本

如果你用時鐘上的秒數來衡量演算法，那麼每次換更快的筆電、改用別的程式語言、或在繁忙的伺服器上跑，答案都會變。這種比較方式毫無用處，因為它衡量的是你的硬體，而不是你的想法。與機器無關的成本就是解方：我們不數秒數，而數抽象的步數，於是答案描述的是演算法本身，而非剛好拿來跑它的那台機器。

把這件事講精確的標準做法是隨機存取機器（RAM model）：我們假設有一份很小的「基本步」清單（一次算術運算、一次比較、讀或寫一個記憶體格、跟隨一個指標），並假裝每個都花一單位時間。那麼演算法在某筆輸入上的成本，就是它所執行的基本步數。真實機器每秒跑某個固定數量的這種步驟，所以實際牆鐘時間大約是（那個常數）乘以（我們的步數）。由於漸進記號本來就會丟掉常數倍率，這個未知的機器常數便直接消失：一個花 c 乘 n^2 步的演算法，在每台機器上都回報為 Theta(n^2)。

這正是教科書能在不指名任何電腦的情況下宣稱「合併排序是 O(n log n)」，而且數十年後在當時無人想像的硬體上依然成立的原因。誠實的限制是：RAM model 假設每個基本步成本大致相同、且數字都能放進一個格子；對於非常大的數字（此時加法並非常數時間）或記憶體階層效應（快取未命中遠慢於命中），這個抽象可能誤導，因此存在更精細的模型。