問題的編碼（problem encoding）

在我們能問「這要花多久？」之前，必須先講定什麼算是輸入、又該怎麼把它寫下來。電腦不會直接「看到」十七這個數或「這張圖」；它看到的是一串符號——位元，或紙帶上的字元。問題的編碼就是那套講好的配方：把一個真實物件（一個數、一張圖、一份工作清單）變成這樣的字串，再把字串讀回成原來的物件。它是抽象問題與演算法真正啃食的具體位元組之間的橋樑。

為什麼要計較這個？因為輸入的「規模」——我們拿來衡量執行時間的那個量——取決於編碼，而草率的選擇會騙人。拿一個整數 N 來說。若用二進位（或十進位）寫，大約要 log N 位數，所以輸入規模約為 log N。若改用「一進位」把它寫成 N 個記號，規模就是 N，呈指數級地更大。一個跑 N 次迴圈的演算法，在一進位編碼下看起來是「對輸入線性」，在二進位編碼下卻是「對輸入指數」——同一個演算法，相反的判決。整門學科誠實的慣例是採用自然、簡潔的二進位編碼：數用二進位、圖用鄰接串列或鄰接矩陣，如此一來輸入規模隨「資訊量」成長，而不是隨「數值」成長。

好消息是，對我們真正在乎的問題，只要編碼「合理」，確切是哪一種其實很少有影響。二進位對十進位、鄰接串列對鄰接矩陣，彼此只差一個多項式因子，所以「能否在多項式時間內解出」並不會改變。該避開的是那些病態編碼，尤其是一進位數，它人為地灌大輸入規模，能讓一個真正困難的問題看起來很容易。每當你讀到「輸入規模 n」或「多項式時間」，底下都預設了一種合理的二進位式編碼。