基本步驟（basic step）

基本步驟是一單位的工作，我們約定把它算作固定的同樣成本，不論輸入怎麼成長。當我們說某演算法「要花約 n 步」，就得說清楚什麼是一步——否則這個計數毫無意義。訣竅是挑選一些簡單操作，每個都確實只花有界的時間，然後就數演算法執行了幾個。這就像用數均勻分布的籬笆樁來估算一趟公路旅程的長度：每根樁是一單位，所以數樁就量出了距離。

在標準的隨機存取機器模型裡，基本步驟就是那些各花一單位成本的原始操作：讀或寫一個記憶體格、對字組大小的數做一次算術運算（加、減、乘、除）、一次比較、一次指派，以及跟隨一個分支或跳躍。關鍵性質是每個都有界——它不會隨 n 成長而變貴。所以像「m = A[i]」這樣的單行是常數個基本步驟，而一個每趟做常數工作量的迴圈「for i = 1 to n」總共執行約 n 個基本步驟。我們刻意不去追究每個微操作的精確數目；我們數那些佔主導地位的基本步驟，這足以看出執行時間如何按比例變化。

什麼算基本，是一項建模選擇，選得好能讓分析保持誠實。把一次比較當成基本步驟，對排序能塞進一個字組的數字而言沒問題，但比較兩個上千字元的字串其實不是一步——它可能花與字串長度成正比的時間，假裝不是的話會低估真正的成本。功夫在於為手邊的問題挑選成本確實有界的基本步驟。挑對了，數步驟就給出忠實的圖像；挑錯了，一個隱藏、會成長的成本就可能不知不覺潛入。