【資料結構與演算法】 01 Introduction

# 【資料結構與演算法】 01 Introduction [TOC] <hr> ## Part 0. 為什麼需要 Data Structures and Algorithms? Data structures and Algorithms : for writing good Program - **Space Resources** $\to$ Data structure - momory - disk(s) - transmission bandwidth - **Computation Resources** $\to$ Algorithm - CPU(s) - GPU(s) - computation power - Other Resources - manpower - budget usually cared by management --- ## Part 1. Accessing Algorithms 好的 Data Structure 需要拿出來與放進去的方法。 ### GET Generally assume to **read without deleting** - GET-BY-INDEX : for arrays - GET-NEXT : for sequential access - GET(key) : for search > Often-GET $\iff$ place "nearby" (常用到的東西會放的近一點) ### INSERT Generally assume to **add without overriding** - INSERT-BY-INDEX : for arrays - INSERT-AFTER : for sequential access - INSERT(key, data) --- ## Part 2. Maintenance Algorithms 資料結構的隱含成本 : 維護所需花費的時間 (esp. REMOVE & UPDATE) ### CONSTRUCT - usually possible with multiple INSERT - sometimes possible to be faster than so ### REMOVE - often viewed as deleting after GET - $\sim$ UNINSERT : often harder than INSERT ### UPDATE - usually possible with REMOVE + INSERT - can be viewed as INSERT with overriding --- ## Part 3. **INSERT** of Ordered Array ### SWAP Version 先插入在最後，再移動到適當的位置。 ```c++= // INSERT(A, data) n = A.length A[n+1] = data // put in the back for i=n downto 1 if A[i+1] < A[i] SWAP(A[i], A[i+1]) // cut in consecutive else return ``` ### Direct Cut-in Version 先找到適當的位置，再插入該位置。 ```c++= // INSERT(A, data) key = data i = A.length while i > 0 and A[i] > key A[i+1] = A[i] i = i - 1 A[i+1] = key return ``` --- ## Part 4. **CONSTRUCT** of Ordered Array ### Selection Sort 從未排序中，取得最小值，放在已排序部分的最後。 <img src='https://he-s3.s3.amazonaws.com/media/uploads/2888f5b.png'> #### 虛擬碼 ```c++= // SELECTION-SORT(A) for i=1 to A.length GET-MIN-INDEX(A,i,A.length) SWAP(A[i],A[m]) return A // GET-MIN-INDEX(A,l,r) m = l // store current min.index for i=l+1 to r // update if i-th element smaller if A[m] > A[i] m = i return m ``` ### Insertion Sort Sequential 整個序列，把當前 element 插入適當的位置。 > CONSTRUCT with multiple INSERT <img src='https://miro.medium.com/v2/resize:fit:818/1*_NOe6jL9veyR4yAyf85dzA.png'> #### 虛擬碼 ```c++= // INSERTION-SORT(A) for i=1 to A.length INSERT(A,i) return A // INSERT(A,m) key = A[m] i = m-1 while i > 0 and A[i] > key A[i+1] = A[i] i = i - 1 A[i+1] = key ``` --- ## Part 5. **REMOVE and UPDATE** of Ordered Array ### REMOVE ```c++= // REMOVE(A,m) i = m + 1 while i < A.length A[i-1] = A[i] // fill in i = i + 1 A.length = A.length - 1 ``` ### UPDATE ```c++= // UPDATE(A,m,data) key = data i = m if A[i] > key // insert to front i = i - 1 while i > 0 and A[i] > key A[i+1] = A[i] i = i - 1 A[i+1] = key else // insert to back i = i + 1 while i < A.length and A[i] < key A[i-1] = A[i] i = i + 1 A[i+1] = key ``` --- ## Part 6. Sequential Search Algorithm SEQ-SEARCH : structurally similar to GET-MIN-INDEX #### Review of GET-MIN-INDEX ```c++= // GET-MIN-INDEX(A,i,r) m = l // store current min.index for i=l+1 to r // update if i-th element smaller if A[m] > A[i] m = i return m ``` ### Sequential Search ```c++= // SEQ-SEARCH(A,key,l,r) for i = l to r // return when found if A[i] equals key return i return NIL ``` ### Sequential Search with Shortcut 若是在已排序的情況下，有機會可以提早結束。 ```c++= // SEQ-SEARCH-SHORTCUT(A,key,l,r) for i = l to r // return when found if A[i] equals key return i else if A[i] > key return NIL return NIL ``` --- ## Part 7. Binary Search Algorithm Binary Search can multiple shortcuts by quickly checking the middle #### 虛擬碼 ```c++= // BIN-SEARCH(A,key,l,r) while l <= r m = floor((l+r)/2) if A[m] equals key return m else if A[m] > key r = m - 1 // cut out end else if A[m] < key l = m + 1 // cut out begin return NIL ``` #### 程式碼 ( java.util.Arrays ) ```java= private static int binarySearch(int[] a, int key) int low = 0; int high = a.length - 1; while (low <= high) { int mid = (low + high) >>> 1; int midVal = a[mid]; if (midVal < key) low = mid + 1; else if (midVal > key) high = mid - 1; else return mid; // key found } return -(low + 1) // key not found ``` --- ## Part 8. Conclusion ### Trade-off Different Factors good program needs understanding trade-off - faster GET $\iff$ slower INSERT and/or maintenance - more space $\iff$ faster computation - harder to implement/debug $\iff$ faster computation ### Summary of Data Structure - Definition of data structure : organize data with access/maintenance algorithms - Ordered array as data structure : insert by cut-in, remove by fill-in - GET (search) in ordered array : binary search using order for shortcuts - why data structures and algorithms : study trade-off to move from coding to programming --- ## Appendix :question: 生成測試資料的技巧 1. 思考什麼情形最容易出錯，例如最極端情形/邊緣情形 (boundary case)，需思考到全面狀況 2. 如何生成大規模測試資料