Introduction to Algorithms Third Edition
- 問題
- 問題的難度
- 由問題的規則決定問題的難度
- 會影響computation model
- 限制魔術方塊只能往前轉，就會增加解題的難度
- 解決問題的定義
- 用了兩個反證法來說明擂台法的正確性
- 證明j*是最大的
- j*=1的情況，不需要執行for loop，直接return j
- j*>1的情況，比j大執行for loop，j被換成j*，最後回傳j
- 證明困難度不能再比n-1更低
- 如果是n-2的話,就會存在有兩個第一名,沒有辦法分出勝負
- problem instance就是input
- 任何的input都要能夠滿足rule(algorithm)
- problem instance:所有輸入的序列串
- algorithm:
- problem-oriented programming
- 用執行的速度衡量演算法的好壞
- 多個輸入經過演算法的處理之後產生唯一正確答案
- 生活中的演算法，用最少做最好
- 少用遞迴，用for while代替
- 遞迴是用stack的方式來存放未處理的函式
- 不但當前的問題沒有解決還會產生很多子問題(以2的n次方產生問題)
