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

比較低次項與所提出的主導項：

這並不是說線性項從精確公式中消失，而是說它相對 $n^2$ 愈來愈小；配合正首項，便可支持緊確的 $\Theta(n^2)$ 結論。

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

在固定字長 RAM model 中，每句只執行一次，連續語句的成本相加後仍是 $\Theta(1)$。若 a、b 是 bit 長度隨輸入增長的 arbitrary-precision integer，就必須另外計算算術操作的成本。

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

迴圈主體恰好執行 $n$ 次，而且每次都有常數成本，所以總成本是 $an+b=\Theta(n)$，其中 $a>0$ 及 $b$ 為固定常數。課件中的 Average function 也是一次完整掃描加上最後一次除法；呼叫它是 $\Theta(n)$ 操作，不能因為原始碼只寫一行 function call 便當作常數成本。

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

這段程式的內層語句恰好執行 $n\cdot n$ 次，所以成本為 $\Theta(n^2)$；結論來自迴圈邊界，而不是只因為看見兩個 loop 關鍵字。

Function call 也可能把乘法隱藏起來。課件中的 naive variance routine 在 $n$ 次迴圈中，每次都呼叫成本為 $\Theta(n)$ 的 Average(array,n)，所以主體工作為 $\Theta(n^2)$；最後再計算一次 average 只增加 $\Theta(n)$。若先在迴圈外計算 mean，多個連續線性階段的成本相加便成為 $\Theta(n)$。如果使用臨時儲存，還須另行報告 auxiliary-space cost。

同一計數方法也適用於非矩形迴圈。如果內層由 i + 1 運行至 n - 1，執行次數是 $\sum\limits_{i=0}^{n-2}(n-i-1)$，即三角形求和；如果 index 每一輪加倍，則由 $2^k<n$ 得到 $k=\Theta(\log n)$；如果內層上界為 i，就必須計算 $\sum\limits_i i$，不能寫成 $n$ 乘一個固定數。因此真正需要分析的是迴圈邊界描述的 iteration space，而不是原始碼中出現多少個 for。

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(n-1)/2$。把 $n$ 換成 $2n$ 或 $10n$，主導二次式的比值分別趨近 $4$ 與 $100$。這解釋了課件中的計時趨勢；真正證明漸近類別的是計數定理，而不是有限數據表。

取 $C=1,n_0=1$，則所有 $n\ge1$ 都有

再由 $(n^2+n)/2\ge n^2/2$ 得到下界，所以緊確結論是 $\Theta(n^2)$。$O(n^3)$ 雖然也正確，卻不夠精確。

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

前提是已排序、可隨機存取的陣列，而且 key comparison 為常數時間。第一次 probe 便命中時，best-case cost 為 $\Theta(1)$；worst case 中，每一輪至多保留一半候選項，因此為 $\Theta(\log n)$。這個 midpoint 寫法避免 left + right overflow。

搜尋失敗時仍有相同的對數 worst-case bound：候選區間不斷縮小，直至變成空。若允許重複 key，這個版本可以回傳任何一個 matching position；尋找第一個或最後一個 matching position 則需要修改 invariant。Binary search 也不會免費把未排序搜尋變成對數成本：預先排序的成本只有在足夠多次後續查詢共同分擔時才值得支付。Linked list 不能以常數時間定位 midpoint，因此 random-access assumption 是複雜度結論的一部分，而不是無關的 implementation detail。

若演算法不斷把問題對半分解，直至 subproblem 的規模為一，而且每一遞歸層的總合併工作為 $\Theta(n)$，則共有 $\Theta(\log n)$ 層，總成本為 $\Theta(n\log n)$。等價地，對二次冪規模， $T(n)=2T(n/2)+\Theta(n)$ 有這個解；一般規模的 ceilings 與 floors 只會改變常數。必須證明「每層線性工作」這個前提；divide-and-conquer 形式本身並不保證此界。

逐層求和描述的是時間，不會自動給出空間界。若兩個 recursive call 依次完成， active call depth 為 $\Theta(\log n)$，而 merge 使用的臨時儲存仍可能達到 $\Theta(n)$。改變 implementation 或改為 parallel execution，可能改變空間輪廓，卻不一定改變計算 total work 的 recurrence，所以必須始終清楚指出正在界定哪一種資源。