看到 n,就知道該寫什麼:時間複雜度與最大子陣列和

開一個新系列:讀 Antti Laaksonen 的 Competitive Programmer’s Handbook(CPHB)。這本書是 CSES Problem Set 的配套教材,線上 PDF 免費,三十章從複雜度一路講到幾何,薄、密、沒有廢話。

網路上 CPHB 的筆記和題解很多,這個系列想做三件不一樣的事:

每一篇都從暴力解開始,問它浪費了什麼。 更快的解法,幾乎都是看出了一個暴力解沒用上的結構。這是貫穿全系列的主軸。
每一篇都有可以親手操作的動畫。 一步一步往前、往後,也可以改輸入重跑。靜態的圖只能給結論,動畫讓你看見那一步到底省在哪裡。
每一篇都有一段「這招在哪裡上班」,把競賽技巧接回 Production——接得上就接,接不上就老實說。

第一篇是全書的地基:時間複雜度,以及書上用來示範它的經典題——最大子陣列和。

一秒鐘能做幾件事

時間複雜度是用來估算演算法有多快的工具:把基本運算的次數寫成輸入大小 $n$ 的函數,只留最大的那一項、忽略常數。

估算的起點只有一個數字:現代電腦一秒大約能做數億次基本運算。有了這個數字,就能在寫程式之前先判斷:題目時限一秒、 $n = 10^5$ ,你想的解法是 $O(n^2)$ ——那就是 $10^10$ 次運算,要跑數十秒。還沒寫就知道不行。

反過來用更有力:看到 $n$ ,就能反推題目要的複雜度。

每一列的運算量都落在 10⁷~10⁸ 上下——表上的上限就是這樣算出來的。題目給的 n 等於在告訴你答案大概長什麼樣子。(表格依原書 Ch2〈Estimating efficiency〉)

原書用 C++,這張表也是照 C++ 的速度算的。這個系列的程式碼用 Python——CSES 收 Python 3 和 PyPy3——所以要記得 Python 的常數大約比 C++ 慢一個數量級以上:同樣一秒,安全的運算量要抓在 $10^7$ 上下,表上每一列的 $n$ 都要再保守一點, $O(n^2)$ 大概只敢用到 $n \le 2000$ 。

這張表是競賽選手看題目的第一個動作。 $n \le 20$ 的題目在暗示「可以窮舉子集」; $n \le 10^6$ 的題目在暗示「排序或掃一遍,而且只有這兩條路」。它直接幫你劃掉一半的思路。

但要記得原書的提醒:複雜度只是估計,它藏起了常數。 同樣是 $O(n)$ ,可能是 $n/2$ 次,也可能是 $5n$ 次——實際跑起來差十倍。

怎麼算出複雜度

原書 Ch2 的計算規則,收斂成四條就夠用:

程式長相	複雜度	例子
$k$ 層巢狀迴圈,每層跑 $n$ 次	$O(n^k)$	兩層迴圈比較所有配對 → $O(n^2)$
幾段程式接著執行	取最慢那一段	$O(n) + O(n^2) + O(n)$ → $O(n^2)$
有兩個輸入大小	兩個都要寫	外層 $n$ 、內層 $m$ → $O(nm)$
遞迴	呼叫次數 × 每次的成本	每次呼叫自己一次、遞迴 $n$ 層 → $O(n)$ ;每次呼叫自己兩次 → $O(2^n)$

範例:最大子陣列和

給一個陣列,找出和最大的連續一段。書上的例子:

$[-1,\ 2,\ 4,\ -3,\ 5,\ 2,\ -5,\ 2]$

答案是 10,也就是 $[2, 4, -3, 5, 2]$ ——中間那個 $-3$ 要吞下去,因為兩邊加起來比它大。陣列裡有負數,這題才有意思。原書允許空子陣列,所以答案至少是 0。

這題有三個解法,複雜度分別是 $O(n^3)$ 、 $O(n^2)$ 、 $O(n)$ 。三個解法看的其實是同一個東西:所有子陣列排成的一個三角形。

從 1 到 2,撿回的是「array[a..b] = array[a..b−1] + array[b]」;從 2 到 3,撿回的是「同一欄只需要最好的那一個起點」。綠色格子在同一列連成一段 = 接著前一欄留下的那格往右延伸;換到另一列 = 前面的和是負的,從自己重新開始。

演算法 1:O(n³),每個區間從頭加

最直接的做法:用 a、b 固定區間的頭尾,再用第三層迴圈把 array[a..b] 加起來。

best = 0
for a in range(n):
    for b in range(a, n):
        sum = 0
        for k in range(a, b + 1):
            sum += array[k]
        best = max(best, sum)

浪費在哪:算 array[0..3] 的時候,array[0..2] 剛剛才算過——但它把那個和丟掉,從頭再加一次。

演算法 2:O(n²),同一列接著加

把剛剛丟掉的撿回來: $\text{sum}(a..b) = \text{sum}(a..b-1) + \text{array}[b]$ 。右端每往右一格,只要再加一個數。第三層迴圈消失了。

best = 0
for a in range(n):
    sum = 0
    for b in range(a, n):
        sum += array[b]
        best = max(best, sum)

還浪費在哪:它還是把三角形裡每一格都算過一次。可是對同一個結尾 b 來說,我們只在乎「以 b 結尾的最大和」——其他起點根本不用看。

演算法 3:O(n),Kadane

換個問法:以位置 $k$ 結尾的最大子陣列和是多少? 只有兩種可能:

只有 array[k] 自己;
以 $k-1$ 結尾的某一段,再接上 array[k]——既然要最大,接的那一段也該是「以 $k-1$ 結尾的最大和」。

所以每一格只要跟前一格的答案比一下:

best = sum = 0
for k in range(n):
    sum = max(array[k], sum + array[k])
    best = max(best, sum)

sum 是「以 $k$ 結尾的最大和」,best 是一路看過來最大的那個。(正式的程式碼別拿 sum 當變數名,它會蓋掉 Python 的內建函式;這裡為了跟原書對照才沿用。)一個迴圈, $O(n)$ 。這也是能做到的最好——任何解法至少得把每個元素看過一次。(這個解法因 Jon Bentley 的 Programming Pearls 而出名,書中把它歸功於 J. B. Kadane。)

動手跑一次:暴力解和 Kadane 賽跑

下面把演算法 2 和 Kadane 並排,兩邊共用同一個時鐘,每一步各做一次加法。按「→」一步一步走,或按播放;也可以換成自己的陣列,或按「隨機」。

(這裡是互動動畫,需要 JavaScript。兩邊答案都是 10:O(n²) 暴力解要做 36 次加法,Kadane 只做 8 次。)

$n = 8$ 時是 36 次對 8 次,看起來還好。但暴力解的次數是 $n(n+1)/2$ , $n = 10^5$ 時大約 $5 \times 10^9$ 次;Kadane 還是 $10^5$ 次。

如果想慢慢看 Kadane 為什麼對,下面這個只放 Kadane,每一格拆成兩步:先決定「接上去還是重新開始」,再決定「要不要更新 best」。特別留意 sum 變成負數之後的那一格——那就是「前面的和是負的,接上去只會更小」的時刻。

(這裡是互動動畫,需要 JavaScript。)

原書的實測

原書在一台電腦上跑了隨機輸入(不含讀檔時間):

$n$	演算法 1 $O(n^3)$	演算法 2 $O(n^2)$
$10^2$	0.0 s	0.0 s
$10^3$	0.1 s	0.0 s
$10^4$	> 10.0 s	0.1 s
$10^5$	> 10.0 s	5.3 s
$10^6$	> 10.0 s	> 10.0 s
$10^7$	> 10.0 s	> 10.0 s

$n$ 小的時候三個都一樣快——複雜度的差距只有在 $n$ 變大時才會現形。 這也是為什麼 n 小的測試資料永遠抓不到效能問題。

浪費了什麼

把三個解法排在一起看,每一次變快都是撿回一份浪費:

1 → 2:相鄰區間的和只差一個數,不用重算。
2 → 3:同一個結尾只需要最好的起點,其他起點不用看。

兩次撿回來的都是同一種結構——子問題的答案可以重複用。本系列把它標成 【重疊】,第 6 篇的動態規劃就是把這件事做成一套方法。

這招在哪裡上班

寫之前先估算。 一支要比對「所有配對」的批次作業,資料是一千筆還是一千萬筆,決定了它是 1 秒還是要跑好幾天。同一張表在 SQL 裡也適用:沒有等值條件的 self-join 就是兩層迴圈,看執行計畫其實就是在看複雜度。
常數會咬人。 複雜度藏起來的常數,在 Production 裡常常是一次網路往返。迴圈裡每一圈打一次資料庫,同樣是 $O(n)$ ,比一次查回來慢上幾個數量級——這種差距複雜度看不出來,得靠量測。
驗收別人給的解。 AI 很快就能寫出一個 AC 的解,但它在 $n = 10^5$ 時會不會超時,是驗收的人要回答的問題。拿題目的 $n$ 對一下上面那張表,是最便宜的第一道檢查:不用跑,就有證據說它過不過得了。這是驗收的手藝在演算法上的版本。

練習

CSES Maximum Subarray Sum:注意 CSES 這題要求非空子陣列,全部是負數時答案是最大的那個負數,不是 0——best 不能從 0 開始。

反思

我跟競賽的距離

先說清楚我的位置:我沒有什麼競賽經歷,不是 IOI 或 ICPC 那條路出來的。我有的是 LeetCode——累積解了大約 1500 題,打週賽有一次進到前 50。所以這個系列不是「選手教你刷題」,是一個刷了很多題、然後在業界做了很多年後端的人,回頭把這本書重讀一次,看哪些東西真的留下來了。

留下來最多的,就是這篇講的這件事:看到資料量,先在腦袋裡算一次。 這不是什麼高深的技巧,但它是我每天都在用的那一個。

工作上用得最多的,是估算

日常開發很少需要自己寫演算法——排序、雜湊表、索引,語言和資料庫都包好了。但「這個計算過程跑得完嗎」這個問題天天在問,而答案幾乎都是從資料庫 table 的數據量推出來的:這張表現在幾百萬筆、一年後幾千萬筆,這段邏輯要掃它幾次、有沒有跟另一張表做配對——把這些數字套進去,就知道這個做法是幾秒、幾分鐘,還是根本跑不完。上面那張表的思路,換成 table 的筆數照樣成立。

我工作上真的自己實作演算法的一次,是在 mobile 上做本機的片語前綴搜尋,用的是壓縮 trie。那個故事留到第 24 篇字串那篇再講;這裡想說的是,那一次要先回答的問題,跟這篇是同一個——資料有多大、每次查詢能花多少時間,所以能用什麼結構。

當面試官時,我在看什麼

我自己當面試官出演算法題,題目不會出得太難,大多數人都解得出來。因為我要看的不是「解不解得出來」,而是解的過程裡的那些細節:怎麼跟我討論題目、怎麼釐清條件、卡住的時候怎麼互動,還有寫出來的東西有沒有品味。一題難到沒人解得出的題目,這些全部看不到。

這跟上面那張表是同一件事:題目本身不是重點,看到 $n$ 之後的那個反應才是——你會不會先停一下,算一算這個規模允許什麼做法,再動手。這個反應在面試裡看得到,在工作上更看得到。