輸入規模（input size）

輸入規模是這份工作有多大，用一個我們稱為 n 的數字來衡量。為十個名字排序是小工作；為一千萬個排序則是大工作。要談演算法的執行時間如何成長，我們得先有一把公平的尺，量出每筆輸入「有多大」——這把尺就是輸入規模。對一串清單，n 通常是項目的個數；對一段文字，n 是字元數；對一張圖，我們常用兩個數字：頂點數與邊數。

更仔細地說，輸入規模指描述該實例所需的資料量，常用項目個數來計，或更嚴格地用寫下它所需的位元數來計。嚴格版本對數字很重要：整數 1000000 的數值是一百萬，但只需約 20 個位元就能寫下，所以它作為輸入的「規模」約是 20，而非一百萬。這正是為什麼一個執行時間取決於數值（而非位元數）的演算法，可能暗中是輸入規模的指數時間。我們把成本表示成 n 的函數——比方說約 n 次比較、約 n^2，或約 n log n——這樣才能問出真正的問題：當 n 加倍，工作量會怎樣？

選對規模的衡量方式是一項建模決定，草率的選擇會誤導人。對兩個 n 位數相乘來說，規模是位數的個數，而不是數字本身的大小。對圖演算法而言，只說一個「以 n 表示」的界限是含糊的，除非你說清楚 n 算的是頂點、邊，還是兩者。先把規模的衡量方式釘死，後面所有關於速度與成長的陳述才真正有意義。