ADA Lecture 1: Introduction

如何設計一個好的演算法

• 效率
  • 時間:節省一個人一秒的時間，就相當於拯救人的生命(Steve job)
  • 空間:硬碟相較於以往便宜，但還是有限制
• problem instance(個例)
  • 如何找出陣列中最大的數值(擂台法:一個一個比大小)
  • 逐一去比大小的hardness(n-1)
  • computation model的規則會影響解決問題的難度
• hardness
  • 問題的防禦力
  • upper bound(防禦力)越低越好 => best case
  • lower bound(攻擊力)越高越好 => worse case
  • 兩個match再一起就是optimal algorithm
• 如何定義解決一個問題
  • 用反證法證明一個問題是有正確的解法(可以正確的解決問題)
  • 用不同的情境驗證同一個解法可以得到同樣的結果
• computation model
  • 解決問題的條件和規則
  • 解魔術方塊(只能用直的和橫的轉，不能夠整個拆下來)

ADA Lecture