[資料結構(Data Structure, DS)] 演算法評估與資料型別

1. 漸近符號(Asymptotic Notation)
2. Big-Oh( Ο )
3. Omega( Ω )
4. Theta( Θ )
5. 常用數學公式

漸近符號(Asymptotic Notation)

• 以等級(Order)的方式來評估演算法的好壞
• 為何要用漸近符號來評估演算法?
  • 演算法即使執行次數不同，但在電腦上執行的效能可能差不多
  • 不同指令的執行時間本來就不同，單看次數原本就不準
    • 浮點數加法執行時間 > 整數加法執行時間

  • for(int i = 0; i <= n; i++)
        a = (b+c)/d+e;
    

    T(n) = n

  • for(int i = 0; i <= n; i++) {
        a = b+c;
        a = a/d;
        a = a+3;
    }
    

    T(n) = 3n;
• 漸近符號表示方法：
  • Big-O( Ο )
  • Omega( Ω )
  • Theta( θ )

Big-Oh( Ο )

• Big-Ο代表演算法時間函式的上限(Upper bound)
  • 在最壞的狀況下，演算法的執行時間不會超過Big-Ο
• • f(n) = Ο(g(n)) iff ∃正常數c和n₀，使得f(n) ≤ c × g(n), ∀ n >= n₀
  • 讀音：f of n is big oh of g of n
    • n：輸入資料大小
    • f(n)：理想狀況下，程式在電腦中實際執行指令次數
    • g(n)：執行時間的成長率
  • 若輸入資料量(n)比(n₀)多時，則時間函數f(n)必會小於等於g(n)
    • 當輸入資料量大到一定程度時，則c×g(n)必定會大於實際執行指令次數
  • cg(n)相當於f(n)的上限，在最壞情況下(Worst Case)，f(n)的成長率最多到g(n)，而不會超過它
    
• 時間函式的Big-O Notation導出步驟
  • 係數設為1
  • 保留最大項，刪除其它項
  • • T(n) = 3 O(1)
  • • T(n) = 2n + 3 1n + 1 O(n)
  • • T(n) = 3n² + 4n + 5 1n² + 1n + 1 O(n²)
• 常見時間複雜度及函式成長率
  • 除非確定輸入資料量(n)很小，一般不會允許使用指數階或階乘時間複雜度的演算法
  
  

  成長函式的值
  log n	n	n log n	n2	n3	2n
  0	1	0	1	1	2
  1	2	2	4	8	4
  2	4	8	16	64	16
  3	8	24	64	512	256
  4	16	64	256	4096	65536
  5	32	160	1024	32,768	4,294,967,296

• 常數階	線性階	對數階	線性乘對數階	平方階
  i = 1; j = 5; i = i * j;	i = 1; while( i < n) { i++; }	i = 1; while( i < n) { i = i*2; }	i = 1; while ( i <= n) { j = 1; while ( j <= n) { j = j*x; } i = i + 1; }	i = 1; while ( i <= n) { j = 1; while ( j <= i) { j = j+1; } i = i + 1; }
  T(n) = 3 ⇒ O(1)	T(n) = n ⇒ O(n)	T(n) = log2n ⇒ O(log2n)	T(n1) = n, T(n2) = log2n ⇒ T(n) = T(n1) × T(n2) = nlog2n ⇒ O(nlog2n)	T(n1) = n, T(n2) = T(n)/T(n1) = (n+1)/2 ⇒ T(n) = 1 + 2 + ... + n = n × ( n + 1)/2 ⇒ O(n2)

• f(n) = 5n + 3, 求c與n₀
  • f(n) = 5n + 3 f(n) = Ο(n)
    由f(n) = Ο(g(n))可知g(n) = n
  • 令c為最大項的常數值加1
    f(n) = 5n + 3 c = 5 + 1 = 6
  • f(n) = 5n + 3 ≤ cg(n)
    f(n) = 5n + 3 ≤ 6n --- 兩邊同減5n
    3 ≤ n
    n至少要≥3 n₀ = 3
  • f(n) = Ο(g(n)) iff ∃正常數c=6和n₀=3，使得f(n) ≤ c × g(n), ∀ n >= n₀
• f(n) = 2n² + 3n + 4, 求c與n₀
  • f(n) = 2n² + 3n + 4 f(n) = Ο(n²)
    由f(n) = Ο(g(n))可知g(n) = n²
  • 令c為最大項的常數值加1
    f(n) = 2n² + 3n + 4 c = 2 + 1 = 3
  • f(n) = 2n² + 3n + 4 ≤ cg(n)
    f(n) = 2n² + 3n + 4 ≤ 3n² --- 兩邊同減2n²
    3n + 4 ≤ n² --- 兩邊開根號
    n至少要≥4 n₀ = 4
  • f(n) = Ο(g(n)) iff ∃正常數c=3和n₀=4，使得f(n) ≤ c × g(n), ∀ n >= n₀

Omega( Ω )

• Ω代表演算法時間函式的下限(Lower bound)
  • 在最好的狀況下，演算法的執行時間不會比Omega快
• • f(n) = Ω(g(n)) iff ∃正常數c和n₀，使得f(n) ≥ c × g(n), ∀ n >= n₀
    • n：輸入資料大小
    • f(n)：理想狀況下，程式在電腦中實際執行指令次數
    • g(n)：執行時間的成長率
  • 若輸入資料量(n)比(n₀)多時，則時間函數f(n)必會大於等於g(n)
    • 當輸入資料量大到一定程度時，則c×g(n)必定會小於實際執行指令次數
  • cg(n)相當於f(n)的下限，在最好情況下(Best Case)，f(n)的成長率最多到g(n)，而不會低於它
    
• f(n) = 5n + 3, 求c與n₀
  • f(n) = 5n + 3 f(n) = Ω(n)
    由f(n) = Ω(g(n))可知g(n) = n
  • 令c與最大項的常數值相同
    f(n) = 5n + 3 c = 5
  • f(n) = 5n + 3 ≥ cg(n)
    f(n) = 5n + 3 ≥ 5n --- 兩邊同減5n
    3 ≥ 0 恆真 n₀可為任意值
    令n₀為1
  • f(n) = Ω(g(n)) iff ∃正常數c=5和n₀=1，使得f(n) ≥ c × g(n), ∀ n >= n₀
• f(n) = 2n² + 3n + 4, 求c與n₀
  • f(n) = 2n² + 3n + 4 f(n) = Ω(n²)
    由f(n) = Ω(g(n))可知g(n) = n²
  • 令c與最大項的常數值相同
    f(n) = 2n² + 3n + 4 c = 2
  • f(n) = 2n² + 3n + 4 ≥ cg(n)
    f(n) = 2n² + 3n + 4 ≥ 2n² --- 兩邊同減2n²
    3n + 4 ≥ 0 恆真 n₀可為任意值
    令n₀為1
  • f(n) = Ω(g(n)) iff ∃正常數c=2和n₀=1，使得f(n) ≥ c × g(n), ∀ n >= n₀

Theta( Θ )

• Θ代表演算法時間函式的上限與下限
• • f(n) = Θ(g(n)) iff ∃正常數c₁,c₂和n₀，使得c₁ × g(n) ≤ f(n) ≤ c₂ × g(n) , ∀ n ≥ n₀
    • n：輸入資料大小
    • f(n)：理想狀況下，程式在電腦中實際執行指令次數
    • g(n)：執行時間的成長率
    • c₁×g(n)：下限 Ω
    • c₂×g(n)：上限 Ο
  • 若輸入資料量(n)比(n₀)多時，則存在正常數c1與c2，使c₁×g(n) ≤ f(n) ≤ c₂×g(n)
  • If f(n) = Ο(g(n)) & f(n)=Ω(g(n)), then f(n) = Θ(g(n))
  • c₂g(n)相當於f(n)的上限，c₁g(n)相當於f(n)的下限
    
• f(n) = 5n + 3, 求c₁、c₂與n₀
  • f(n) = 5n + 3 f(n) = Θ(n)
    由f(n) = Θ(g(n))可知g(n) = n
  • 由之前Ω和Ο的範例可得 c₁=5, c₂=6
  • f(n) = 5n + 3 ≥ c₁ g(n), f(n) = 5n + 3 ≤ c₂g(n)
    f(n) = 5n + 3 ≥ 5n, f(n) = 5n + 3 ≤ 6n ---別各減5n
    3 ≥ 0, 3 ≤ n 令n₀=3
  • f(n) = Θ(g(n)) iff ∃正常數c₁=5,c₂=6和n₀=3,使得c₁ × g(n) ≤ f(n) ≤ c₂ × g(n), ∀ n ≥ n₀

常用數學公式