基礎觀念2026-07-2930 min read

Day 9:程式寫得好不好?時間複雜度

大 O 符號是估計程式變慢速度的量尺,必背 O(1) 到 O(n²) 五個等級,學會看迴圈疊幾層直覺判斷複雜度。

寫得出程式只是第一步,寫得「好不好」才是真功夫。今天要學的大 O,就是用來評估「程式跑得快不快」的量尺。這是 13 天轉職甄試衝刺大綱的 Day 9。

📅 前言:為什麼流量一高,伺服器可能會爆炸?

同一個功能,可以用「聰明的寫法」或「笨拙的寫法」實作出來。資料量小的時候兩者可能感覺不出差別,但當資料量從 100 筆變成 100 萬筆,笨拙的寫法可能會慢到讓伺服器直接卡死。時間複雜度,就是用來估計「程式會隨著資料量增加,變慢的速度有多快」。

大 O(寫作 O(...))是一種「估計」,不是精確算出「幾秒鐘」,而是描述「當資料量(通常用 n 代表)變大時,程式大概會變慢多少倍」。

💡 生活比喻: 想像你要在電話簿裡找一個名字。「從第一頁翻到最後一頁,一個一個看」跟「因為電話簿是按照字母排序的,所以用猜的方式,每次都翻到中間、越猜越接近」——資料量越大,這兩種方法花的時間差距會越來越誇張。大 O 就是在描述這種「差距的等級」。

甄試常常不會直接問你「這是什麼複雜度」,而是給你一段程式碼,叫你判斷。三個直覺判斷法:

1. 單層迴圈跑 n 次 ➔ O(n)

for (let i = 0; i < n; i++) {
  console.log(i);
}

2. 兩層迴圈,各跑 n 次(巢狀迴圈)➔ O(n²)

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    console.log(i, j);
  }
}

💡 判斷技巧: 看迴圈「疊了幾層」。疊一層通常是 O(n),疊兩層通常是 O(n²),以此類推。

3. 每次都把範圍砍一半(像猜數字)➔ O(log n)

例如明天要學的「二分搜尋」,每猜一次就排除一半的可能範圍,所以就算資料有 100 萬筆,通常猜不到 20 次就能找到答案——這就是 O(log n) 比 O(n) 快得多的原因。