禮拜一、二翹掉，不然Hashing就看完了，唉。
有錯請指教。
知道怎麼寫Algo，就知道怎麼操作，舉個例子便能知道Stability。
知道怎麼寫Recursive time fcn，就知道時間複雜度。
Thm:
- Binary Search
- 給定 n筆records，求 比較過程之Decision Tree決策樹
- 給定 n筆records，求 最多比較次數
Decision Tree高度，即高度最小化的BT
- 給定 要找的數，求 比較次數
- 用Decision Tree來描述sorting(採用comparison-based skill)之比較過程
Decision Tree是BT，non-leaf是比較node，leaf是排序結果
- 給定 n筆records，求 最多比較次數
Ω(n*log n)，即 Decision Tree高度-1 >= ([log n!]+1)-1 ≒ n*log n
- Selection Problem
- Find min & max 找min & max
T(n) = 3n/2
用遞迴，n筆需要，2筆比1次決定大小，n-2筆找好大小的分別跟2筆大小再比1次，
算recursion time fcn
- Select ith smallest item among unsorted n data n個找第i小資料
用quick sort，只要找一邊。
- avg, best O(n)
- worst O(n^2)，可用middle of three or medium of mediums選pk改善
假設k為偶數(k為奇數要微調)
T(n) = O(n) + O(n) + T(n/k) + O(n) + T(3n/4+k)
k >= 5 O(n)，k < 5 O(n*log n)
1. 每k個組一group，將n個data切成n/k個group，
除一個可能不足每個group有k個data O(n)
2. 每個group各自排序(n/k)*O(k^2) = O(k*n) = O(n)
3. 每個group第k/2個data是該group之median，共n/k個median，
遞迴找出n/k個medians之median(n/k個找第n/2k個小資料)作為pk T(n/k)
4. 用q=Partition(A,p,r)在A[p],A[r]間把pk放到正確位置A[q]，O(n)
5. i=pk直接回傳，i比pk小 select(A,p,q-1,i)，i比pk大 select(A,q+1,r,i-k)
(至少有一半的groups(1/2)*(n/k)-1 pk所在的group -1 不足k個data的group)
*(k/2)
= n/4-k 個比pk大的data
所以有3n/4+k個比pk小的data
最差花T(3n/4+k)，要從3n/4+k個找第i小的資料
Search Algo:
- Linear Search (iterative)
- with sentinel哨兵
Array or Link list(Data movement較Array少)
O(n)，(1+...+n)/n = (n+1)/2
- Binary Search (iterative or recursive)
Data Comparison較Linear Search少
divide and conquer, prune and search
Array
O(log n)
Sort Algo:
初等
- Insertion Sort (插入前面排好的，順便排)
適合資料量少(Internal Sort)
Stable
Sorting in-place
time(comparison) avg O(n^2) ~ O(n)
space O(1)，r, A[0]=-∞
- Binary Insertion Sort
time(comparison, movement) O(n^2)
- Linear Insertion Sort
time(comparison, movement) O(n^2)
- Selection Sort (右邊剩下，找最小交換至左)
適合大型紀錄(一筆紀錄由很多欄位組成)，因為每一回合頂多SWAP一次
Unstable
Sorting in-place
可以用或不用if(檢查是否是min，來決定是否用SWAP)
time O(n^2)
space O(1)，min, temp in SWAP fcn
- Bubble Sort (由左而右兩兩交換，最大升最高 or 由右而左兩兩交換，最小降最低)
Stable
Sorting in-place
time avg O(n^2) ~ O(n)
space O(1)，flag(檢查有無SWAP), temp in SWAP fcn
- Shell Sort (n/2^k型 或 2^k-1型 或 自訂型)
Unstable
Sorting in-place
time avg O(n^2) ~ 一般O(n^(3/2))
space O(1)，flag, temp in SWAP fcn