这篇是写给修ds课的学弟，通常有经验的人很少写心得

这篇是写给修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满有趣的。

这也说明为何O(.)这些算法不考虑常数，N小时本来就不用在意，但别忘了N不大不小时就得小心常数，像做hash table时许多人把table size开太小，这是很明显的错误，没想到的话，表示分析做得不够扎实。

不得中行而与之，必也狂狷乎？

推荐系列文章：”日本动画产业舞台的前与后”