演算法的靈魂 —— 學會看效率,才不會寫出資料一多就當掉的程式。
同一段程式,在你的舊筆電跑 3 秒、在新桌機跑 0.5 秒——但它的 Big O 是一樣的。因為我們問的不是機器多快,而是:當資料從 100 筆變成 100 萬筆,你的程式是「差不多快」還是「慢到天荒地老」?
看懂 Big O,你才有能力在兩種寫法之間,一眼看出哪個會爆、哪個能撐。之後學任何演算法,都是回頭在跟它打交道。
1. 看趨勢,不看秒數。我們關心「資料變兩倍,工作量會變幾倍」,而不是實際的時鐘時間。
2. 看最壞情況。Big O 通常描述「運氣最差時最多要做幾次」,這樣才有保證。
3. 丟掉常數和小項。O(2n) 會簡化成 O(n);O(n² + n) 會簡化成 O(n²)。資料夠大時,最兇的那一項說了算。
冰箱裡 5 罐還是 500 罐,伸手拿第一罐的時間都一樣。資料再多,工作量不變。
翻到中間,太前面往後、太後面往前,每翻一次範圍砍一半。字典厚一倍也只多翻一次。
30 人發 30 次,60 人發 60 次。人數變兩倍,時間就老實地變兩倍。
每個人跟其他每個人握一次。人數變兩倍,握手次數卻衝到快四倍。
拖動滑桿改變資料量 n,看每種複雜度各要做「幾次動作」。你會親眼看到 O(n²) 和 O(2ⁿ) 怎麼瞬間失控。
O(n²)。O(log n)。O(n)。O(n) 降到 O(1),最常用的加速手法。從最爽的 O(1) 一路到最慘的 O(n!),每個都附「為什麼是這個複雜度」,右上角可一鍵複製。
❌「O(1) 就代表很快」 —— 不對。O(1) 代表「跟資料量無關」,它可能做一件很慢的事,但不管資料多大都只做那一次。
❌「O(100n) 比 O(n) 差」 —— 常數會被丟掉,兩個都是 O(n)。Big O 看的是成長趨勢,不是倍數。
❌「Big O 只用來看時間」 —— 也用來看空間複雜度(吃多少記憶體)。同一套符號,兩種用途。
判斷下面三段的時間複雜度各是 O(什麼):
把你的答案跟理由打到對話裡,我會告訴你對不對、卡在哪。