今日進度：

ch 6 - ch 8

下週(3/25)要小考

範圍是 ch 2 、 ch 3 、 ch 4 、 ch 6 、 ch 7 、 ch 8

ch 2 

‧ 分析演算法： a. increamtal        ex: Insertion sort

                b. divide & conquer  ex: Marge sort

‧ Insertion sort 的時間複雜度最佳是 O(n) ； 最差是 O(n^2)

‧ Marge sort 的時間複雜度最佳最差都是 O(nlgn)

ch 3

‧ Θ Tight Bound : f(n)=Θ(g(n)) → c1 * g <= f <= c2 * g

‧ Ο Upper Bound : f(n)=Ο(g(n)) → f <= cg
   ο             : f(n)=ο(g(n)) → f <  cg

‧ Ω Lower Bound : f(n)=Ω(g(n)) → cf <= f
   ω             : f(n)=ω(g(n)) → cf <  g

‧ 兩個方程式 f、g 只有四種關係 Θ+Ο+Ω 或 Ο+ο 或 Ω+ω 或 沒有關係

ch 4

‧ 簡化 T(n)=aT(n/b)+f(n) ： 代入化簡 、 樹狀圖 、 Master theory

ch 6

‧ Build a heap = Ο(n)

‧ Remove the root node = Ο(lgn)

‧ Add a node = 最佳 Ο(1) 最差 Ο(lgn)

ch 7

‧ Quicksort = 最佳 Ο(nlgn) 最差 Ο(n^2)

‧ 不限定數字的排序法最佳時間複雜度為Ο(nlgn) ( 用decision tree證 )

ch 8

‧ Counting sort : 有n個小於<k的整數的排序

   用陣列儲存每個數字出現的次數 再依序輸出 時間複雜度是Ο(n)

‧ Radix sort : n個固定位數的數字( ex 三位數，小數也可 ) 時間複雜度Ο(n)

‧ Bucket sort : 先把n個東西分類成小堆簡化問題再排序 時間複雜度Ο(n)