決定性與非決定性計算（deterministic vs nondeterministic computation）

決定性演算法徹底可預測：給它同樣的輸入，它總做同樣的事、回傳同樣的答案，像一台販賣機，按同樣的鈕每次都給你同樣的零食。你寫的多數演算法都是決定性的。有趣的替代品從兩個截然不同的方向鬆開這一點——一個實用（隨機演算法，會擲硬幣），一個理論（非決定性計算，會神奇地猜）——把它們分清楚很值得，因為它們聽起來相似，意思卻不同。

決定性演算法的下一步，完全由它當前的狀態與輸入所決定；它整段執行是單一、可重複的路徑。隨機演算法被允許在過程中做真正隨機的選擇——它有一個擲硬幣的來源——所以同樣的輸入可能導致不同的執行。我們於是談它的期望執行時間（對硬幣結果取的平均）或它正確的機率。隨機快速排序是經典案例：藉由隨機挑選樞紐，它以 O(n log n) 的期望時間執行，這裡的期望是對隨機樞紐取的，而非對輸入取的。非決定性計算則是另一頭理想化的怪獸：想像一台機器，在每個選擇點都能同時探索所有選項，且只要任何一串猜測能導向接受，就宣告它接受。這不是你能造出的真實裝置；它是用來把問題難度分類的思考工具，也是複雜度類 NP 裡的那個「N」。

把這三者分清楚能避免真正的誤解。隨機並不是含糊地指「草率」或「通常對」——它的保證是精確的機率陳述，而且關鍵在於，隨機快速排序的最壞情況仍是 O(n^2)；只有它的期望時間才是 O(n log n)。非決定性根本不是指「隨機」——NP 機器那種神奇的猜測，不是硬體能做到的，而且「NP」絕不是在主張某問題需要指數時間，只是說一個提議的解能被快速檢查。把非決定性與隨機性混淆，或把期望時間與最壞情況時間混淆，是整門學科裡最常見的初學者錯誤之一。