[公開課閒聊] 計算機概論第十一講 Algorithm - 台大 于天立

Ped隨手摘

1. 如何評斷演算法表現
2. 會受機器等其他因素影響
   1. 計算執行時間
   2. 執行的數量
3. 相關指標
   1. Big-O
      1. f(n) 屬於 O(g(n)) f(n) upper bound 不會超過 big O 
      2. 指數為n總是比多項式為n來的大 ex.n100次方 屬於(=) O(2n次方)   computer science在這裡常把屬於寫成=
      3. 只在意n極大時的是否能bound住
         1. 不在意n小的時候的表現? n如何算小該如何定義? n很大的時候Big-O仍然比f(n)表現好嗎?
   2. Big-Omega
      1. f(n) 屬於 O(g(n)) f(n) lower bound 不會超過 big Omega
   3. Big-Theta
      1. f(n)既是Big-O又是Big-Omega
4. 主要先抓三種情境 best、worst、average
   1. 因為表現會被輸入資料影響所以才需區分情境
   2. 分析通常最重視 average 有時為了預期最壞的情況會注意worst比較少注意 best的情境
5. 演算法主要issue
   1. 運算結果正確
   2. 效能
6. loop須注意三個屬性
1. precoditions
   1. 進入前的狀況
2. loop invariants
   1. 在loop中不會改變
3. Termination condition
1. 最後停止loop的條件