3.1 複雜度增長與演算法成本

點解要先講複雜度

lecture slides 一開始就講 growth，而唔係先講 micro-optimization，係有 原因嘅。當輸入規模 n 變大時，成本點樣放大通常比某一部機快幾多更 重要。

Big-O 係一個增長模型，唔係計時器。唔同機器會改變 constant factor， 但唔會改變線性、二次、對數呢啲基本形狀。

呢個定義係一個 proof obligation。你要證明上界，而唔係只係話「睇落似 二次」。

化簡規則唔係偷步，而係重點

tutorial slides 重複強調兩條規則：

• 當 n 夠大時，刪走影響愈來愈細嘅項，
• 刪走 constant factor。

所以

0.1n^3 + 10000n^2 + n + 3

最後仍然係 $O(n^3)$。cubic term 會慢慢主導其他所有項。同樣，

(n^2 + n)/2

嘅增長率仍然係 $O(n^2)$，因為 1/2 唔會改變漸近形狀。

CSCI2520 常見增長級別

課程入面反覆用到同一組 class。

• O(1)：直接存取、已知指標重連、簡單算術。
• O(log n)：對半縮減搜尋、平衡樹查找、反覆除 2。
• O(n)：掃描 array 或 linked list。
• O(n log n)：分治加上每一層嘅線性工作。
• $O(n^2)$：雙重掃描，尤其係比較密集嘅 double loop。

for (int width = 1; width < n; width *= 2) {
  for (int i = 0; i < n; i += 2 * width) {
    merge_block(i, width);
  }
}

個 comparator widget 係視覺輔助，唔係 derivation 嘅代替品。你應該先寫 出增長式，再用 widget 去確認 intuition。

由程式讀出複雜度

最快嘅方法，通常係搵出最常執行嘅部分，再數佢跑幾多次。

int x = a + b;
int y = x * 2;
return y;

int sum(const int a[], int n) {
   int total = 0;
   for (int i = 0; i < n; i++) {
      total += a[i];
   }
   return total;
}

int countPairs(int n) {
   int c = 0;
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
         c++;
      }
   }
   return c;
}

一個具體排序例子：selection sort

tutorial deck 用 selection sort 去示範 quadratic growth 點樣出現。 算法會喺剩餘 suffix 入面搵最細元素，再 swap 去正確位置。

void selectionSort(int a[], int n) {
   for (int i = 0; i < n - 1; i++) {
      int min = i;
      for (int j = i + 1; j < n; j++) {
         if (a[j] < a[min]) {
            min = j;
         }
      }
      if (min != i) {
         int tmp = a[i];
         a[i] = a[min];
         a[min] = tmp;
      }
   }
}

比較次數大約係

(n-1) + (n-2) + ... + 1 = n(n-1)/2.

呢個和係二次，所以演算法係 $O(n^2)$。slide 裡面用文字講嘅重點都一樣： 當 n 加倍，時間大約變成 4 倍。

comparison sort 同 non-comparison sort

sorting slides 再進一步指出：merge sort、heapsort 同 quicksort 都係 comparison sort。

對 comparison sort 而言，worst-case comparisons 有 Ω(n log n) 嘅 lower bound。即係話，任何 comparison sort 都唔可以喺 worst case 打破呢個漸近 界限。

如果想快過呢個 lower bound，就要避免用 comparison 做主要機制。呢個就係 counting sort 同 radix sort 嘅意義。

• counting sort 喺 key range k 可控時可以係 linear time。
• radix sort 會逐個 digit 做 stable subroutine sorting。
• counting sort 唔係 in-place comparison sort。

實際重點唔係「所有 sort 都一樣」，而係資料域同操作模型會決定應該用咩 複雜度類別。

點解 lower terms 同 constants 會消失

tutorial 嘅 simplification slide 有好多類似：

$N + 1 = O(N)$

同

$N^3 + 1000N^2 + N = O(N^3)$.

原因係最快增長嘅項會主導長遠增長。低階項仍然存在，但當 n 大到某個 程度之後，就唔再重要。

best case、worst case、average case

同一個演算法，單靠一個複雜度標籤未必夠。唔同輸入安排，可以令成本表現 完全唔同。

• Best case：最有利輸入下嘅成本；
• Worst case：最昂貴輸入下嘅成本；
• Average case：喺某個概率模型之下嘅平均成本。

binary search 就係一個好例子。

int binarySearch(const int a[], int n, int target) {
   int left = 0, right = n - 1;
   while (left <= right) {
      int mid = (left + right) / 2;
      if (a[mid] == target) return mid;
      if (a[mid] < target) left = mid + 1;
      else right = mid - 1;
   }
   return -1;
}

所以你見到複雜度聲稱時，一定要問：而家講緊邊個 case？如果冇特別講， 通常默認係 worst case。

divide-and-conquer 同 n log n 形狀

slide deck 提到 merge-sort 類結構，因為呢個正正係 n log n 最典型嘅例子。

標準推理分兩層：

• 每一層都處理線性數量嘅資料；
• 總層數大約係 log n。

所以總成本就會變成 n log n。

讀 code 時嘅複雜度檢查表

當你見到一段新 code，最穩妥嘅順序係：

1. 搵出邊個操作重複得最多；
2. 數清楚外層 loop、recursion，或者 traversal 會令佢跑幾多次；
3. 分開 constant work 同 size-dependent work；
4. 等數清楚之後先做化簡。

如果你跳過計數，通常最後就只係估。好嘅 complexity analysis 係先慢慢讀， 再做短而準確嘅分類。

constants 仍然點樣重要

漸近記號描述嘅係長遠形狀，但唔代表 constants 永遠唔重要。當 n 仲細， 一個簡單嘅 $O(n^2)$ routine，實際上仍然可能跑贏一個隱藏常數好大嘅 O(n log n) routine。

所以較完整嘅結論通常分兩步：先將增長類別分清楚，再判斷目前輸入規模 係咪仍然受常數因素影響。

stack 同 queue 操作嘅成本

上一節 ADT 內容其實正好提供呢一節嘅具體例子。當 representation 定咗， 同一個 interface 仍然可以有唔同成本。

• array-based stack push / pop 通常係 constant time，但 resize 時會貴啲。
• linked-list queue 如果 head 同 tail 維護得好，enqueue / dequeue 可以係 constant time。
• QueueLength() 如果要掃 linked list，就可能係 linear time；如果有長度 欄位，就可以係 constant time。

所以漸近分析一定要同實作細節一齊睇，唔可以分開。

重點總結

複雜度分析係用嚟理解 scaling，而唔係估邊個 implementation「感覺上快啲」。 如果你可以搵到主導重複動作、寫出計數、再正確化簡，通常就可以唔跑程式都 分類到演算法。