效率分析的重要性

這篇是寫給修DS課的學弟，通常有經驗的人很少寫心得，可能是懶得寫，或是東西太多不知寫什麼好，太多資訊等於沒有資訊，讓讀的人無所適從。針對別人需求回答，反而能輕易寫出不錯的文章。

---

學DS、Algorithm最重要的是一開頭教的效率分析 (O(.)，Theta(.)，Omega(.))，現成的lib一堆，任何領域的人都能輕易使用，但要用對時機 就要懂得分析，還有懂得DS、Algorithm的特性，至於有能力設計DS、Algorithm，那是更之上的能力，效率分析是其根基。

以Bubble Sort來說，分析後會發現它是Theta(N^2)，也就是最糟和最好都要做N^2次，更糟的是swap和comparasion都是O(N^2)，selection sort的swap至少是O(N)。

多練習分析，就會分析的更順，多練習思考best case，worst case，average case，這不僅幫助效析，也能幫助設計test case來驗證程式。

很多推論不需要背，比方我之前說linked-list不適合sort，分析index的情況，就能明白不管是comparasion還是swap，linked-list都是O(N)，遠遜於array表示的O(1)。

為何insertion sort搭linked-list就不錯? 可以練習一下，insertion sort是滿特別的sort，分析看看best case，worst case滿有趣的。

另外關於上篇推文提的bubble sort在 N < 10時滿快的，這個數據有兩個問題：

1. N太小時，都是瞬殺，實務上時間搞不好是花在I/O或CPU的分工上，參考依據不足
2. N太小時，再快也沒意義，最糟的方法還是很快結束

這也說明為何O(.)這些算法不考慮常數，N小時本來就不用在意，但別忘了N不大不小時就得小心常數，像做hash table時許多人把table size開太小，這是很明顯的錯誤，沒想到的話，表示分析做得不夠扎實。