複雜度計算

Introduction

• Definition by Algorithm: An algorithm is a finite set of instructions that if followed, accomplishes a particular task . In addition, all algorithms must satisfy the following criteria.

• 演算法是一組有限的指令集合，若依序執行，便能完成某項特定任務。 此外，所有演算法必須符合以下幾項條件。

  1. Input. Zero or more quantities are externally supplied. 輸入零個或是多個數值

  2. output. 演算法必須產生至少一個結果。

  3. definiteness(確定性). Each instruction must be clear and unambiguous.每一條指令都必須是明確且無歧義的，不能讓執行者產生混淆。

  4. finiteness(有限性). 演算法必須在有限步驟內結束，不能無限執行。

  5. effectiveness(有效性) .每一條指令都必須是非常基本的，以至於理論上人類只用紙筆就能執行它。 僅僅像第三項（criterion 標準確定性）那樣定義清楚還不夠；它還必須是可行的（實際能做到的）。

• Selection sort algorithm

  • 找到最小的元素(\(a[j]\))，交換當前的元素(\(a[i]\)) \(tmp:=a[i]; \ a[i]:=a[j]; \ a[j]:=tmp;\)

   Algorithm SelectionSort(a,n)
   {
   	for i := 1 to n do
   	{
   		j:=i;
   		for k=i+1 to n do
   			if (a[k] < a[j]) then j:=k;
   		tmp:=a[i]; a[i]:=a[j]; a[j]:=tmp;
   	}
   }
  

C 與 C++ 的參數傳遞

在 C/C++ 中，參數傳遞方式會影響變動空間需求：

1. C style 陣列

   • 函式參數 int A[] 或 int A[100] 都退化為 int* A（指標），表示傳址（call-by-address），不會複製陣列。

   • 若要模擬 call-by-value（複製整個陣列），必須手動分配並 memcpy：

      void bar_by_value(int A[], int n) {
      int* copy = (int*)malloc(n * sizeof(int));
      memcpy(copy, A, n * sizeof(int));
      // SP(I) = Θ(n)
      free(copy);
      }
     

   • 直接傳指標時：

      void bar_by_address(int A[], int n) {
      // SP(I) = Θ(1)
      }
     

2. C++ 容器（std::vector / std::array）

   • 值傳遞 std::vector<int> v：會複製底層陣列 → \(SP(I)=\Theta(n)\)

   • 參考傳遞 const std::vector<int>& v：不複製 → \(SP(I)=\Theta(1)\)

   • 同理，std::array<int,N> 若以值傳遞亦會複製整個陣列物件。

3. C++ 真參考（reference）

   • 使用 int& x：純參考傳遞，可直接修改呼叫端變數 → \(SP(I)=\Theta(1)\)

   • 與指標類似，但語法更直觀。

   void incrementRef(int& x) {
    x++;
   }
   
   int main() {
    int a = 5;
    incrementRef(a);
   }
   

4. C++ 指標傳遞（Call-by-Address）

   • 使用指標參數，直接傳入變數位址 → 不複製資料

   void increment(int* x) {
    (*x)++;
   }
   
   int main() {
    int a = 5;
    increment(&a);
   }
   

Space Complexity

• 總空間需求

• \(c\)：程式本身或固定配置所需的常數空間

• \(SP(I)\)：變動空間需求（分析時重點）

• 變動空間 \(SP(I)\) 包含

  1. 資料結構本身：動態配置的陣列、物件、鏈結串列、樹⋯⋯
  2. 參數傳遞
     • Call-by-value：值會複製 → 可能需要 \(O(n)\) 空間
     • Call-by-address/reference：只傳位址 → \(O(1)\) 空間
  3. 遞迴呼叫棧：每層呼叫的參數與局部變數都要壓到呼叫棧上

• 分析重點

  • 忽略常數 \(c\)，只看 \(SP(I)\) 隨 \(n\) 增長的量級
  • 若無動態結構也不遞迴 → \(SP(I)=O(1)\)
  • 若遞迴深度為 \(d\)，每層 \(O(1)\) → \(SP(I)=O(d)\)
  • 若動態配置長度為 \(n\) 的陣列 → \(SP(I)=O(n)\)

範例

1. 純迴圈、無動態配置 \(SP(I) = O(1)\)

   void foo(int n) {
       int x = 0;
       for (int i = 0; i < n; i++) {
           x += i;
       }
   }

2. 遞迴計算階乘 \(n ⇒ SP(I) = O(n)\)

int fact(int n) {
    if (n <= 1) return 1;
    return n * fact(n - 1);
}

3. call-by-address(reference) \(SP(I) = O(1)\) vs. call-by-value \(SP(I) = O(n)\)

void bar(int A[], int n);         

void bar(int B[], int n) {        
    int* copy = new int[n];
    // ...
}

Asymptotic notation

Definition

• \(g(n)\) 是指一個基準還數有可能是\(nlog(n)\) 或是 \(log(n)\)的基準
• \(O(g(n)) = \{ f(n) \mid \exists\, c > 0,\, \exists\, n_0 > 0,\, \forall n \ge n_0,\ 0 \le f(n) \le c \cdot g(n) \}\)
  1. 表示某個函數 \(f(n)\) 增長速度「最多不會超過」**某個基準函數 \(g(n)\) 的常數倍，當 \(n \ge n_0\) 時就一直成立。
  2. 可使為上界。
• \(o(g(n))= \{ f(n) \mid \exists\, c > 0,\, \exists\, n_0 > 0,\, \forall n \ge n_0,\ 0 \le f(n) \lt c \cdot g(n) \}\)
  1. 嚴格上屆
• \(\Omega(g(n)) = \{ f(n) \mid \exists\, c > 0,\, \exists\, n_0 > 0,\ \forall n \ge n_0,\ f(n) \ge c \cdot g(n) \}\) 2. 表示某個函數 \(f(n)\) 增長速度「會超過」某個基準函數 \(g(n)\)的長數倍數，當 \(n \ge n_0\) 時就一直成立。 3. 可視為下界。
• \(\omega(g(n))=\{ f(n) \mid \exists\, c > 0,\, \exists\, n_0 > 0,\ \forall n \ge n_0,\ f(n) \gt c \cdot g(n) \}\)
  1. 嚴格下界

• \(\Theta(g(n)) = \{ f(n) \mid \exists\, c_1 > 0,\, \exists\, c_2 > 0,\, \exists\, n_0 > 0,\ \forall n \ge n_0,\ c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n) \}\)
  1. 表示 \(f(n)\) 的增長速度恰好等同於 \(g(n)\)，也就是它上下都被 \(g(n)\) 的常數倍包住。
  2. 可是為中間上下界都有。

• ❗️如果 \(f(n) \lt g(n)\)，不代表 \(f(n)\) 的 growth order 比 \(g(n)\) 的 growth order 小是不正確的

• ❗️如果兩個 asymptotic natations 相加取大的那個

Attribute

Trichotomy

漸進符號關係 不 滿足三分律：對任意兩個函數 \(f, g\)，不一定 存在且僅存在下列三種之一：

• 不可比（Incomparable）：有時既不是 \(f=O(g)\)，也不是 \(g=O(f)\)。
• 範例：令l

由於 \(1+\sin n\) 在 \([0,2]\) 間震盪，無法統一找到常數 \(c,n_0\) 使其中一邊恆成立，故這對函數不可比。

Limit Asymptotic Theorem

1. 範例

- 根據極限定理，得到  $f(n)=o(g(n))$

2. 範例：\(f(n)=3n^2-100n+6\) 屬於 \(\omega(n)\) {106 中原資工}

3. 範例：\((n + a)^b\) 是否屬於 \(\Theta(n^{b})\)，且 b 是一個 real constants {106 中原資工}

- 實際上 $(n + a)^b = \Theta(n^b) \quad\Longrightarrow\quad True$。

Log Method

1. \(log(f(n)) = o(log(g(n)) 可保證 f(n) = o(g(n))\)
2. \(log(f(n)) = \omega(log(g(n)) 可保證 f(n)=\omega(g(n))\)
3. 但不保證 \(\log f(n)=\Theta(log \ g(n))\)

各種等價證明

等價 of O, Ω and Θ

• 複雜度小不代表每一個 n 的時候就會比較少的執行時間
• 也不能給 n 一個數值，說某個演算法比另一個快，因為有可能 n 不夠大

Big-O 運算的封閉性（加法 & 乘法）

• \(f(n) = O(s(n)) \wedge g(n) = O(r(n)) \Rightarrow f(n) + g(n) = O(s(n)+r(n))\) 『特性 1.2』

• \(f(n) = O(s(n)) \wedge g(n) = O(r(n)) \Rightarrow f(n) \cdot g(n) = O(s(n) \cdot r(n))\) 『特性 1.2』

• \(f(n) = O(g(n)) \Rightarrow f(n) + g(n) = O(g(n))\) 『特性 1.3』

複雜度計算

Stirling’s Formula

或更精確帶誤差項：

Growth rate (fast to slow)

• Prove \((\lg n)!\)

**證明意義**：由  

可得  

• **Prove \(n^{1/\lg n}=2\)

Prove \(\log(n!) = \Theta(n\log n)\)

簡單來說就是 \(O\) 是利用每一項都最小於 \(\Omega\) 利用數列的後半段當作原本函數的下界，再利用每一項都大於最小項求得。

• 範例：Let \(T(n) = 1 + \frac12 + \frac13 + \cdots + \frac1n\) and assume \(T(n)=\Theta(f(n))\). Derive the simplest formula for \(f(n)\).

Recursive Time function

展開帶入法

考慮遞迴

對 \(T(n)\) 連續展開 \(k\) 次：

令 \(k=n-1\)，則 \(T(n-k)=T(1)=1\)，得到

Master Theorem

Master Theorem 就是一種 直接求解 以下形式遞迴關係的工具：

它特別 適用於 分治（Divide & Conquer）演算法，因為這類演算法通常會把一個大小為 \(n\) 的問題，切成 \(a\) 個大小約為 \(n/b\) 的子問題，然後再做額外的合併工作 \(f(n)\)，這邊的 \(b\) 只有 \(\gt\) 的原因是因為他是切割幾個子問題那麼就需要只寫 \(\gt\)，不然就沒有切割問題了，主要比較的是 \(n^{\log_b a}\) 和 \(f(n)\) 在比較。

• 下圖為解釋 \(n\log_b a\) 由來

  

1. case 1 : if \(f(n) = O(n^{log_b a-\varepsilon}), \varepsilon \gt 0 \Rightarrow \theta(n^{log_b a})\)
2. case 2 : if \(f(n) = O(n^{log_b a}) \Rightarrow \theta(n^{log_b a}\lg n)\)
3. case 3 : if \(f(n) = \Omega(n^{log_b a+\varepsilon}), \varepsilon \gt 0 \ and \ af(n/b) \le cf(n), 0 \gt c \gt 1,\forall n \Rightarrow T(n)=\Theta(f(n))\)

Extended Master Theorem

何時用
形：\(T(n)=a,T(n/b)+f(n)\)，其中 \(a,b\) 為常數、\(b>1\)。
**擴充版（k 版）**用在：\(f(n)\) 與臨界 \(n^{\log_b a}\) 只差一個對數因子 \((\log n)^k\)。

三種情況（k 版） 設 \(d=\log_b a\)。若 \(f(n)=\Theta\big(n^{d}\log^{k} n\big)\)：

• \(k>-1\)：\(T(n)=\Theta\big(n^{d}\log^{k+1} n\big)\)

• \(k=-1\)：\(T(n)=\Theta\big(n^{d}\log\log n\big)\)

• \(k<-1\)：\(T(n)=\Theta\big(n^{d}\big)\)

口訣：差一個 \(\log^{k}\)。\(k>-1\) 多一個 \(\log\)；\(k=-1\) 變 \(\log\log\)；\(k<-1\) 不加 \(\log\)。

判斷流程

1. 算 \(d=\log_b a\)

2. 把 \(f(n)\) 寫成 \(n^{d}\cdot(\log n)^{k}\) 找出 \(k\)

3. 套上面三條結論

範例：

此時 \(a=2\)、\(b=2\)，臨界階 \(n^{\log_2 2}=n\)，而

對應 \(k=1\)。
原始 Master 定理 嘗試比較的是 \(n^1\) 與 \(n\log n\)，可發現 Case 1/2/3 均不符合：

• Case 1 要求 \(n\log n = O(n^{1-\varepsilon})\) → 不成立
• Case 2 要求 \(n\log n = \Theta(n)\) → 不成立
• Case 3 要求 \(n\log n = \Omega(n^{1+\varepsilon})\) → 不成立

故必須使用 Extended Master，代入 \(k=1\) 得

遞迴樹

兩路比例切分的遞迴樹筆記

範例 1：會乘樹高（× \(\log n\)）

\(T(n)=T(n/3)+T(2n/3)+n\)

• 第 \(i\) 層所有子問題規模總和仍是 \(n\)
  ⇒ 該層成本 \(L_i=\Theta(n)\)（層層相同）

• 樹高 \(\Theta(\log n)\)
  ⇒ 總成本 \(=\Theta(n)\times\Theta(\log n)=\boxed{\Theta(n\log n)}\)

ASCII Tree

Level 0:            [ size n | cost n ]                       ⇒ total ≈ n
                   /                     \
Level 1:   [ n/3 | cost n/3 ]      [ 2n/3 | cost 2n/3 ]        ⇒ total ≈ n
            /        \                 /          \
Level 2: [n/9|n/9][2n/9|2n/9]   [2n/9|2n/9][4n/9|4n/9]         ⇒ total ≈ n
...（持續 1/3 與 2/3 切分，所有子問題規模總和仍為 n）...
Level h:  子問題規模總和 ≈ n，節點成本相加仍 ≈ n               ⇒ total ≈ n

樹高 \(h=\Theta(\log n)\)。總成本 \(\sum_{i=0}^{h} n=\Theta(n\log n)\)。

範例 2：不會乘樹高（葉層主導）

\(T(n)=T(n/3)+T(2n/3)+1\)

• 每層成本是「節點數」；葉子數量 \(\Theta(n)\) ⇒ 總成本被葉層主導，\(\boxed{\Theta(n)}\)（沒有多一個 \(\log n\)）

ASCII Tree

Level 0:            [ size n | cost 1 ]                        ⇒ total = 1
                   /                     \
Level 1:   [ n/3 | cost 1 ]        [ 2n/3 | cost 1 ]            ⇒ total = 2
            /        \                 /          \
Level 2: [n/9|1][2n/9|1]       [2n/9|1][4n/9|1]                 ⇒ total = 4
...（每層節點數翻倍；每節點成本固定為 1）...
Level h:   節點數 ≈ 2^h，直到子問題規模到常數；葉子總數 ≈ Θ(n)

各層總成本形成：\(1,2,4,\dots\) 直到葉層總和 ≈ \(\Theta(n)\)。總成本 \(\Theta(n)\)。

介於兩者之間（作對照）

\(T(n)=T(n/3)+T(2n/3)+\dfrac{n}{\log n}\)

• 第 \(i\) 層成本 \(L_i\approx \dfrac{n}{\log n - O(i)}\)
  ⇒ 逐層相加得到 \(\Theta(n\log\log n)\)（乘的是 \(\log\log n\)，不是 \(\log n\)）

一句話結論

是否要「乘樹高」取決於各層總成本是否近乎常數級（如 \(\Theta(n)\)）。
同層總成本平坦 ⇒ 乘樹高；往下遞減 ⇒ 根層主導；往下遞增 ⇒ 葉層主導。