重念一次早該補起來的「資料結構與演算法」。這篇筆記來初步簡介一下 Lowerbounds of Searching & Sorting。
課程相關資訊
[連結]：https://hiskio.com/courses/572/lectures/29825
本篇範圍：Chapter 7
請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。
內容
Comparison Model
先前多數的演算法實踐都是使用 Comparison Model。當你的 comparision 的次數越多，那時間成本就會越高。
Comparison Model 是指整個程式撰寫時，使用 <, <=, >, >=
Decision Tree
Any comparison algorithm can be viewed as a tree at all possible comparisons and their outcomes. The resulting answers are the leaves.
Lowerbounds of Searching
最優解為 log2N。當你採用 comparison model 下，你無論如何優化，都無法低於這個下界。
[ Binary Search & Linear Search ]
Lowerbounds of Sorting
最優解為 N * log2N。當你採用 comparison model 下，你無論如何優化，都無法低於這個下界。
Decision Tree 為： log n! = n log N
[ Bubble Sort, Insertion Sort, Selection Sort, Merge Sort, Heap Sort, Quick Sort ]
