# 入門演算法 --- ## 什麼是演算法 ---- ### 什麼是演算法 - 達成某種目的的過程 - ex: 搜尋資料、對資料進行排序... ---- ### 演算法具備的特性 - 輸入：0 或多個輸入 - 輸出：至少有一個回傳結果（有可能回傳 0 或是 null） - 明確性：每一個指令步驟必須明確 - 有限性：有限步驟後一定會結束，不會進入無窮迴圈 - 有效性：每一個步驟必須與人推演出的結果相符 ---- ### 為什麼要使用演算法 - 做出需求之外 - 執行時間短 - 佔用空間小 - 判斷演算法好壞的標準 - 時間/空間複雜度 ---- O(1) ```javavscript= // O(1) var array = [1 ,2 ,3 ,4 ,5] array.push(6) => [1, 2, 3, 4, 5, ] => [1, 2, 3, 4, 5, 6] ``` ---- O(n) ```javascript= // O(n) var array = [1, 2, 3, 4, 5] array.shift() => [1, 2, 3, 4, 5] => [ , 2, 3, 4, 5] => [2, 3, 4, 5, ] => [2, 3, 4, 5] array.unshift(0) => [1, 2, 3, 4, 5] => [1, 2, 3, 4, 5, ] => [ , 1, 2, 3, 4, 5] => [0, 1 , 2, 3, 4, 5] ``` ---- - O(logn) ex:二元搜尋法 ```javascript= // O(logn) function foo(val) { let input = val let min = 1 let mid = 50 let max = 100 let times = 1 while (true) { console.log('times', times++) console.log(min, '~', max) console.log('mid', mid) console.log('---------------') if (input > mid) { min = mid + 1 } if (input < mid) { max = mid - 1 } if (mid === input) return mid mid = Math.floor((max+min)/2) } } // 每次搜尋刪去一半的可能 ``` ---- - O(n²) ex:選擇排序法 [選擇排序法](https://www.csie.ntu.edu.tw/~b98902112/cpp_and_algo/cpp02/selection_sort.html) ---- ### 時間與空間取捨 - O(1) - O(logn) - O(n) - O(n²) 時間換取空間 or 空間換取時間 --- ## 什麼是資料結構 - 最簡單的資料結構 - 陣列 - 鏈結串列 ---- ### 陣列 Array  - 讀取/更新 O(1) - 新增/刪除 O(n) ---- ### 鏈結串列 Linked list  - 讀取 O(n) - 更新/新增/刪除O(1) ---- ### 結論 - 比較陣列，鏈結串列的優劣勢 - 判斷當下情況 使用適合的演算法或資料結構 | | 讀取 | 更新 | 新增 | 刪除 | | ---- | ---- | ---- | ---- | ---- | | 陣列 | O(1) | O(1) | O(n) | O(n) | | 鏈結串列 | O(n) | O(1) | O(1) | O(1) | --- ## QA