Algorithm (Part I) 大複習

國立臺東大學資訊工程學系

Agenda 1. Insertion Sort 2. Merge-Sort 3.Asymptotic Efficiency 4.Recurrences 5.HeapSort 6.QuickSort 7.Counting Sort 8.RANDOMIZED-SELECT 9.組合考題 -------------------------------------------------- 1.Insertion Sort 考點：一步一步排序 [5,23,12,8,29,14]

2.Merge-Sort 考點：一步一步排序 [7,42,15,29,3,50]

3.Asymptotic Efficiency Ο-notation，0 ≤ 𝑓(𝑛) ≤ 𝑐𝑔(𝑛) Ω-notation，0 ≤ 𝑐𝑔(𝑛) ≤ 𝑓(𝑛) Θ-notation，0 ≤ 𝑐1𝑔(𝑛) ≤ 𝑓(𝑛) ≤ 𝑐2𝑔(𝑛) o-notation，0 ≤ 𝑓(𝑛) ≤ 𝑐𝑔(𝑛)

ω-notation，0 ≤ 𝑐𝑔(𝑛) ≤ 𝑓(𝑛)

考點：排大小並與True&False寫出證明，注意nlogn與log(n!)

常用公式：

4.Recurrences Substitution method Recursion-tree method Master method(漸快、漸近、漸慢) 考點：所有方法對𝑇(𝑛)=?證明常用公式： Recursion-tree

Master Theorem II

5.HeapSort Binary Heap MAX-HEAPIFY Max-Heap-Maximum Max-Heap-Insert 考點：一步一步排序 6.QuickSort Randomized Quicksort 考點：一步一步排序 7.Counting Sort 考點：一步一步排序 8.RANDOMIZED-SELECT 9.組合考題 Describe the scenarios of pivot selection that lead to the worst-case and the best-case in Quick-Sort. Describe the scenarios of input sequence that lead to the worst-case and the best-case in Insertion-Sort. ...