Algorithm Overview [持續更新...]

一: 基礎知識

1. 重點是思考方式, 還有分析效率的技術, 日後才能自行設計新的演算法
2. 在最佳算法尚未知的情況下, 我們可以退一步追尋近似算法, 並且證明此解法不會比最佳解差太多
3. 分析最好/最壞/平均(期望)情況
4. Divide and conquer包含3個步驟: Divide => Conquer => Combine
5. 各排序的時間分析
6. 漸進式符號
7. 解Recurrence的方法: Substitution / Recursion-Tree / Master
   • Substitution:
     • 猜測解
     • 用數歸證明
   • Recursion-Tree:
     • 可以用來幫助猜測解, 再用Substitution證明
     • 或者直接用來證明
   • Master: 當Recurrence符合主定理的3種情況之一時, 可以直接運用主定理證明

二: 排序和順序統計學

1. 排序:
   • 插入排序: n^2, 原地
   • 合併排序: n*log(n), 非原地
   • 堆排序: n*log(n), 原地
     • Max Heapify: 調整節點i與其左右的關係, log(n)
     • Build-Max-Heap: 通過自底而上調用Max Heapify將整個陣列轉成Heap, n
     • HeapSort: n*log(n), 原地
     • Priority Queue: 可用於scheduler, 可用heap實作, 支援以下
       • insert(S,x)
       • maximim(S)
       • extract-max(S)
       • increase-key(S,x,k)
   • 快速排序: 最壞n^2, 平均n*log(n), 原地
     • 通常是排序最佳的實用選擇, 因為平均的效能好
     • 也是基於Divide and conquer的設計
     • 最壞情況: n^2, 每次劃分後的兩個區域分別包含(n-1)與1個元素
     • 最好情況: n*log(n), 每次劃分後的兩個區域元素幾乎相等(~n/2)
     • 平均情況: n*log(n), 只要是按常數比例的劃分(即使是99:1), 都會產生深度為log(n)的遞歸樹
   • 計數排序: k + n
   • 桶排序: n
2. 順序統計: 找第i小的元素

三: 數據結構

四: 高級設計和分析技術

五: 高級數據結構

六: 圖形演算法

七: 演算法研究問題選編

八: 附錄: 數學數學基礎知識