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

Ped隨手摘

1. 演算法表示法
   1. Flowchart (流程圖)
      1. 太複雜的演算法用流程圖難以表達需要靠自己簡化
   2. Pseudocode (P不發音)  虛擬碼
      1. 介於自然語言和程式語言之前，不用嚴謹的語法，主要用來表達想法
2. 問題解決
   1. 分析、了解問題後才有辦法去提出並執行解決計畫，最後再去評估這個解法是否正確與能否用以解其他問題
   2. 老師特別強調分析問題
   3. 通常需要 top-down 和 bottom-up 並行
3. 迴圈
   1. 包含三個必要部分
      1. 迴圈進行前的初始化
      2. 測試條件是否符合繼續的條件
      3. 更改某參數以確定迴圈會結束
4. 插入排序法   未排序資料一次一個， 跟排序好的新陣列中每個值比較，比未排序大的值往下移一個位置，最後會多一個洞放置新資料
5. 二分搜尋法 先拿中間值和目標值比較，較大的話只要搜尋下半部，較小則搜尋上半部，可節省搜尋時間
6. 遞迴
   1. 終止條件需寫在最前面
   2. 由於遞迴會不斷呼叫自己，迴圈的速度會比遞迴快很多，如果可以用迴圈解的話可以考慮使用迴圈
7. 演算法重要技巧
1. divide and conquer (D&C)
   1. 先把問題切分成需多子問題，再一個個解決，二分搜尋法即是此種方式
   2. 每個子問題是獨立的，並不會互相影相
   3. top down
2. dynamic programming (DP)
1. 一樣會先切分許多子問題，各子問題間的結果會互相影響，並產生最後的結果，最短路徑問題即可用此方式解
2. bottom up