Analysis Tools

• 用簡單的主要function來表示複雜度
  1.Polynomial
  2.log
  3.nlogn
  4.Exponential

• 速度比較
  Exponential > 三次 > 二次 > nlogn > 一次 > logn > constant

• Running Time
  要預估一個演算法花的時間，不容易用average time來預估，用worst case來估（不僅比較方便，也比較嚴謹）

• 用實驗來測量performance
  但是這樣很麻煩-->用high-level的方式而不用實際寫出來

• Theoretical Performance Analysis
  1.從seudo code就可預估
  2.不受限於coding language

• Big-Oh Notation
  如果說f(n) = O(g(n))，代表存在兩個正整數c與n0，使得
  f(n) ≤ cg(n) for n ≥ n0

• Big-Oh 規則
  1.若polynomial式為d-degree，則為O(n^d)，可以省略低次方的n跟常數
  2.找“smallest possible class”
  3.最簡單的表示法即可

• Asymptotic Analysis
  通常假設n很大