禮拜一、二翹掉，不然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
---> 我感覺不常考。
高等
- Quick Sort (Hoare左大交換右小，直到兩軍交會 or Comen小的丟至左)
divide and conquer
Unstable
Sorting in-place
time O(n^2) ~ avg O(n*log n)
Hoare資料相同是best，Comen資料相同是worst。由小到大或由大到小都是worst
- 改善worst case方法
- randomized quick sort使用亂數挑pivot key
- middle of three
- median of medians中間鍵之中間鍵
space O(log n) ~ O(n)
源自recursion所要的stack space，stack size取決recursive call深度(次數)
- Merge Sort
(iterative，k-way每個pass每k組一組 or recursive每次呼叫遞迴就是切分成k組)
divide and conquer(recursive)
External Sort
Stable
time O(n*log n)
注意，Merge和Sort(merge sort)部分！！！
- 作2-way merge
Merge:O(n)
每回合merge最少比較次數run1或run2長度，最多比較次數run1+run2長度-1 = n-1
Sort:T(n) = 2*T(n/2) + O(n)
- 沒有Selection Tree 選擇樹，作k-way merge(k runs合併成1 run)
Merge:O(n*k)
Sort:T(n) = k*T(n/k) + O(n*k) = k*T(n/k) + O(n)
- Selection Tree，協助k-way merge加速合併過程
- Winner Tree (與鄰居比較找min)
- Loser Tree (與父點比較找min，較常用因為參與比較的數較少)
- k個runs作k-way merge
Merge:O(k) + O(n*log k)
第一次建樹O(k) + 執行n-2次從k runs比較找min O(n*log k)
Sort:T(n) = k*T(n/k) + O(k) + O(n*log k) = k*T(n/k) + O(n)
- m個runs作k-way merge
Merge:O(m*k) + O(n*log m)
O(每次建Selection Tree需k*共建(k^(h-1)-1)/(k-1)個Selection Tree)
= O(k*(m-1)/(k-1))
= O(m)
O((logk m回合)*(m/k個groups做k-way search)*(k個runs一組)*
(每個run有n/m個data數)*(每次Selection Tree剩下比較次數log k)
= O(logk m*(m/k)*k*(n/m)*(log k))
= O(logk m*n*log k)
= O(n*log m)
Sort:T(n) = k*T(n/k) + O(m) + O(n*log m) = k*T(n/k) + O(n)
space O(n)
space O(n)，暫存每一回合pass之merge結果
- Heap Sort (Bottom up建heap，每回合再執行類似delete-max動作)
Unstable
Sorting in-place
time O(n*log n)，建heap O(n) + 執行n-1回合delete-max動作O(n*log n)
space O(1)，temp in SWAP fcn(最後一點要與root swap)
Linear-Time Sorting method
(採用distribution分派、merge合併，而非comparison-based skill)
- Radix Sort(LSD Radix Sort)
(每回合依某位數分派到bucket完再合併，位數從最小直到最高)
Stable
time O(d*(n+r))，分派O(n)、合併O(r)共d回合
space O(r+n)，link list
O(r*n)，array r個bucket，每個max size n
- Buckets Sort(MSD Radix Sort)
(分派到bucket後各自sorting再合併，分派合併只一次)
Stable
- Counting Sort
(建用作計數的array Count，掃Input計數在Count，Count累加計數，
Input由右而左依Count存的位置放在Output)
Stable
time O(n+k)
O(k) + O(n) + O(k) + O(n)
設定Count皆0 O(k)，掃Input計數在Count O(n)，Count累加計數O(k)，
Input由右而左依Count存的位置放在Output O(n)
where n個input，range 0~k
常用作LSD的subroutine，兩者結合處理range更大的data
即便k是O(n^r)也可用LSD作r回合每次/n再%n，
得到的只有O(r*n)以n為基底的r位數LSD sort，
使得counting sort只有O(n+k) = O(n+n) = O(n)
space O(n+k)
--------------------------------------------------------------------------
以下還未弄懂:
為何有些得random access(array) 有些得sequential access(link list) 上使用
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.226.25.212 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/talk/M.1730480419.A.B8D.html
※ 編輯: OriginalGod (36.226.25.212 臺灣), 11/02/2024 15:47:28