Chapter6-資料結構-Algorithm's Time Complexity and Recursive Program

6.1 Algorithm 的時間複雜度及遞迴程式

---

algorithm 演算法

• 為指令之集合, 用以達到某一特定之任務
• 需滿足:
  1. input ≥ 0 個
  2. output ≥ 1 個
  3. definiteness 明確性: 指令皆是清楚且不模糊的
  4. finiteness 有限性: 在有限的指令數之後會求得結果
  5. effectiveness 有效性: 只可利用紙,筆即可追蹤
• Note:
  Program vs Algorothm => 差別在於4, Program 可以有無窮迴圈

Time Complexity 時間複雜度

• Def:
  • 用來衡量 algorithm 執行時間
  • 利用時間函數: T(n) 表示 隨著資料量的成長, 所需的執行次數之變動
• Ex1: 時間函數計算

i = 1;
while (i <= n)
{
  x = x+1;
}
// 問 line 4 執行次數?
// Sol: T(n) = n

• Ex2:

for(i = 1; i <= n; i++)
{
  for(j = i+1; j <= n; j++)
  {
    x = x+1;
  } 
}
// 問 line5 的執行次數?
// Sol: T(n) = n(n-1) / 2

i	1	2…	n
j	2~n	3~n	n+1~n
x=x+1	n-1	n-2	0

• 思考:
  2n+1
  2n-1
  n+2
  n+100
  n大到一定程度, +1 -1....不重要

漸進式表示法 asymptotic notation

• 於 Time Complexity 中, 常用漸進式來表示一 algo 的時間的成長漸進曲線, 以便快速了解 algo 之複雜程度
• 衡量方式:
  1. Big Oh: upper bound of ƒ(n)
  2. Omega: lower bound of ƒ(n)
  3. Theta: more precision than Big Oh and Omega
• 概念:

Big Oh

• Def: 若 ƒ(n) 為一時間函數, 則 ƒ(n) = O(g(n)) , if and only if 存在兩正數 c 和 n0, 使得 ƒ(n) ≤ c * g(n) , for all n ≥ n0
• Ex1: ƒ(n) = 3n + 2 => O(n) , 因為存在 2 正數, c = 4, n0 = 2, 此時, 3n+2 ≤ 4*n, for all n ≥ 2

定理： ƒ(n) = am*n^m + am-1*n^m-1 +...+ a1*n^1 + a0*n^0, 其中 m 為最高指數項, 則 ƒ(n) = O(n^m)

• Ex2:

ƒ(n) = 3n^5 + 2n^3 + 1000 => O(n^5)
ƒ(n) = 2^n + 1000 => O(2^n)
ƒ(n) = 100 => O(1) 常數

• Ex3: O(logn^2) vs O(n) 誰大?
  = 2log n < O(n)
  2 常數不看

• 常見的 Big Oh: 由小 -> 大排序
  O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(n^3) <…< O(n^c) < O(2^n) < O(n!) < O(n^n)
  越大越複雜

• Proof: ƒ(n) = am*n^m + ...+ a1*n^1 + a0*n^0 = O(n^m)

= ∑ai*n^i ≤ ∑|ai|n^i
          ≤ n^m * ∑|ai|n^i-m
          ≤ n^m * ∑|ai|1
          , for all n ≥ 1
所以故為 O(n^m)

Omega

• Def: 若 ƒ(n) 為一時間函數, 則 ƒ(n) = O(g(n)), if and only if 存在兩正數 C 和 n0, 使得 ƒ(n) ≥ c * g(n), for all n ≥ n0

常見的 Time complexity 求算

• Ex1: T(n) = T(n-1) + n -> 快速排序的 worst case

T(n) = T(n-1) + n
     = [T(n-2) + n-1] + n
     = [T(n-3) + n-2] + n-1 + n
     = [T(n-4) + n-3] + n-2 + n-1 + n
     ....
     = T(n-n) +1+2+...+n
     = (n(n+1))/2
     = (n^2+n)/2
     => O(n^2)

• Ex2: T(n) = 2T(n/2)+n, 求 O(?) -> 快速排序的 Best case

T(n) = 2T(n/2) + n
     = 2[2T(n/4) + n/2] + n
     = 4T(n/4) + 2n
     = 4[2T(n/8) + n/4] + 2n
     = 8T(n/8) + 3n
     ....
     = nT(n/n) + logn*n
     = n + nlogn
     => O(nlogn)

• Ex3: T(n) = T(n/2) + 1, 求 O(?)

T(n) = T(n/2) + 1 // Binary Search
     = [T(n/4) + 1] + 1
     = T(n/4) + 2
     = [T(n/8) + 1] + 2
     = T(n/8) + 3
     ...
     = T(n/n) + log2 n
     => O(log n)

Recursive 遞迴

• Def: 指函式執行過程反覆呼叫自身函式 => self-calling

• 種類:

  1. 直接 recursive: 在程式中直接呼叫自身

  fun()
  {
    ...
    fun() // self-calling
    ...
  }

  2. 間接 recursive: 在程式中先呼叫其他函式, 再由他呼叫到原本的程式
  • Note: 不建議採用, 易發生後續維護上的不易性

  funA()
  {
    ...
    funB()
    ...
  }
  
  funB()
  {
    ...
    funA()
    ...
  }
  // calling cycle

  3. 尾端 recursive: 函式會在最後再次呼叫自身
  • 建議改採用 “iterative”(non-recursive) 方式撰寫, 以提高效能 -> 做 loop 快, 比做 context-switching 快, 節省時間和空間
  • Note:
    • recursive 會採用到系統的「stack」 後進先出
    • recursive & non-recursive 適用性, 沒有誰好誰壞

  fun()
  {
    ...
    fun();
  }

Recursive vs Non-Recursive (iterative/loop)

• Recursive
  • 優點:
    • 特性:
      • 程式精簡 -> 程式較省 space
      • 易理解
      • 表達力更佳
    • Space
      • 暫存變數需求少 (int, temp…)
  • 缺點:
    • Space
      • 執行時需耗用 “stack” 空間 -> 需系統 stack 支援(會一直追加 Mem.)
    • Time
      • 執行時間較久 -> 效率較差(因為需做 function calling)
• Non-recursive
  • 優點:
    • Space
      • 執行時不需耗用 “stack” 空間
    • Time
      • 執行時間較快 -> 效率較好
  • 缺點:
    • 特性:
      • 程式冗長
      • 不易理解
      • 表達力較差
    • Space
      • 暫存變數需求多

常見的 Recursive

Example1: N!

• 提示:
  • N! = 1, if N = 0
  • N! = N * (N-1)!. if N ≥ 1

int F(int N) 
{
  if (N == 0)
    return 1;
  else
    return N * F(N-1);
}

• 呈上例: 問 F(3) = ? 又呼叫 F() 幾次?
• Sol: F(3) -> 3*F(2) -> 2*F(1) -> 1 * F(0), F(3) = 6, 呼叫 F() 4次
• iterative:

int sum(int n)
int sum = 1, i;
{
  for (i=1; i ≤ n; i++)
  {
    sum = sum * i;
  }
  return sum;
}

Example2: Sum(n) = 1+2+…+n 寫出其 Recursive algo.

• 提示:
  • sum(n) = 0, if n = 0
  • sum(n-1) + n, if n = 1, otherwise

int sum(n)
{
  if (n == 0)
    return 0;
  else
    return sum(n-1) + n;
}

// iterative
int sum(int n)
int sum = 0, i;
{
  for (i=1; i ≤ n; i++)
  {
    sum = sum + i;
  }
  return sum;
}

Example3: 費氏數列 (Fibonacci Number)

• 提示:
  • Fn = 0, if n = 0
  • Fn = 1, if n = 1
  • Fn = Fn-1 + Fn-2, otherwise

int F(int n)
{
  if (n == 0)
    return 0;
  else if (n == 1)
    return 1;
  else
    return F(n-1) + F(n-2);
}

n	0	1	2	3	4	5	6	7	8	9	10
Fn	0	1	1	2	3	5	8	13	21	34	55

• 呈上例, 問 F(5) = ? 又呼叫 F() 幾次?
• Sol:

F(5) = F(4) + F(3)
     = F(3) + F(2) + F(2) + F(1)
     = F(2) + F(1) + F(1) + F(0) + F(1) + F(0)
     = F(1) + F(0) + F(1) + F(1) + F(0) + F(1) + F(0)
// F(5) = 5, 含 F(5) 本身共呼叫 15 次

• Note: 變形

if (n == 0 || n == 1)
 return 1;
else
  return F(n-1) + F(n-2);

// Non-recursive algo
int F(int n)
{
  if (n == 0)
    return 0;
  else if (n == 1)
    return 1;
  else
  {
    int a = 0, b = 1, c, i;
    for (i=2; i ≤ n; i++)
    {
      c = a + b;
      a = b;
      b = c;
      // O(n)
    }
    return c;
  }
}

n	0	1	2	3	4	5	6	7	8	9	10
Fn	1	1	2	3	5	8	13	21	34	55	89

• 若 n 輸入 -3, 問結果?
  • 因為 recursive 會耗用 stack, 而 -3 無法收斂, 故 stack 會耗盡 -> stack out of memory

Example4: G.C.D (Greatest Common Divison) 最大公因數

• 提示:
  • G.C.D(A, B) = B, if (A mod B) = 0
  • G.C.D(A, B) = GCD(B, A mod B), if (A mod B) 不等於 0

int GCD(int A, int B)
{
  if (A % B == 0)
    return B;
  else
    return GCD(B, A % B);
}

• 呈上例, GCD(12, 9) = ?
• Sol: GCD(12, 9) -> GCD(9, 3) -> 3
• 又 GCD(9, 12) = ?
• Sol: GCD(9, 12) -> GCD(12, 9) -> GCD(9, 3) -> 3
• iterative

int GCD (int A, int B)
{
  while (A != 0 && B != 0)
  {
    if (A > B)
      A = A % B; // 把餘數給 A, 一直到有一數為 0
    else
      B = B % A
  }
  if (A == 0)
    return B;
  else
    return A;
}

Example5: Binomial coefficient 二項式係數

• 說明:
  
• 提示:
  

int B(int n, int m)
{
  if (m == 0 || n == m)
    return 1;
  else
    return B(n-1, m) + B(n-1, m-1);
}

• Ex1:
  
• Sol:

B(5, 2) = B(4, 2) + B(4, 1)
        = B(3, 2) + B(3, 1) + B(3, 1) + B(3, 0)
        = B(2, 2) + B(2, 1) + B(2, 1) + B(2, 0) + B(2, 1) + B(2, 0)
        = B(1, 1) + B(1, 0) + B(1, 1) + B(1, 0) + B(1, 1) + B(1, 0)
// B(5, 2) = 10
// 含 B(5, 2) 本身就呼叫 19 次

• 思考: 請用更有效率的方法 iterative

int B(int n, int m)
{
  int a = 1, b = 1, c = 1;
  for (int i = 1; i ≤ n; i++)
  {
    a = a * i; //n!
  }
  for (int i = 1; i ≤ m; i++)
  {
    b = b * i; // m!
  }
  for (int i = 1; i ≤ n-m; i++)
  {
    c = c * i; // (n-m)!
  }
  return a/(b*c);
}
// 易有 overflow

// Solution:
// k = max(n-m, m)
for (int i = n; i > k; i--)
{
  a = a * i;
}
for (int i = 1; i ≤ n-k; i++)
{
  b = b * i;
}
return a / b;

// 將後面剔除可減少, 但不知哪個數值較大, 因此需要找出較大值, 將其除掉

Example6: Ackerman’s

• 背: A(1, 2) = 4, A(2, 1) = 5, A(2, 2) = 7
• 提示:
  • A(m, n) = n+1, if m = 0
  • A(m-1, 1), if n = 0
  • A(m-1, A(m, n-1)), otherwise

int A(int m, int n)
{
  if (m == 0)
    return n+1;
  else if
    return A(m-1, 1);
  else
    return A(m-1, A(m, n-1));
}

• 呈上例: A(2, 2) = ?, 又 A() 呼叫幾次?
• Sol: 7, 呼叫27次

Example7: Tower of Hanoi (河內塔)

• 說明: 3 pegs(柱子) problem
• Recursive algorithm

void Hanoi (n:disc, A, B, C:pegs)
{
  // A 來源, B 中繼, C 目的
  if (n == 1)
    move disc from A to C;
  else
  {
    Hanoi(n-1, A, C, B); // 1
    move the disc n from A to C; // 2
    Hanoi(n-1, B, A, C); // 3
  }
}

• Ex1: 試列出 n = 3 的移動順序

• Sol:

  1. move 1 from A to C
  2. move 2 from A to B
  3. move 1 from C to B
  4. move 3 from A to C
  5. move 1 from B to A
  6. move 2 from B to C
  7. move 1 from A to C

• Ex2: 令T(n)為搬動 n 個 disc, 所需的次數, 則 T(n) = T(n-1) + 1 + T(n-1)

T(n) = T(n-1) + 1 + T(n-1)
     = 2T(n-1) + 1
     = 2[2T(n-2) + 1] + 1
     = 4T(n-2) + 3
     = 4[2T(n-3) + 1] + 3
     = 8T(n-3) + 7
     ...
     = 2^n * T(n-n) + 2^n - 1
     = 2^n - 1
// 時間複雜度為 O(2^n)

Example8: Permutation (排列組合)

• 概念:
  • n個 data 會有 n! 種組合
  • Ex: data a, b, c 之 permutation, 若有 3 筆data => 3! = 3 * 2 * 1 = 6
  • abc, acb, bac, bca, cab, cba
• 思考: Perm(a, b, c)

a + perm(b, c)
b + perm(a, c)
c + perm(b, a)

• Recursive (in C)

void perm (char list[], int i , int n)
{
  if (i == n)
  {
    for (int j = 1; j ≤ n; j++)
    {
      printf("%c", list[j]);
    }
  }
  else
  {
    for (int j = i; j ≤ n; j++)
    {
      swap(list[i], list[j]);
      perm(list, i+1, n);
      swap(list[i], list[j]);
    }
  }
}