重念一次早該補起來的「資料結構與演算法」。這篇筆記來初步簡介一下 合併演算法。
課程相關資訊
[連結]：https://hiskio.com/courses/572/lectures/29810
本篇範圍：Chapter 6
請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。
內容
合併演算法會運用到 two pointer ( 用作兩個陣列各自的 index ) 和 recursion 遞迴 ( 用作拆分 array ) 的技巧。由於每一次進行 merge 都會需要新開一個陣列，所以會吃空間
1. 合併演算法必須是兩個 sorted 的陣列
2. divide & conquer – 拆成重複的小塊累積 (遞迴)，然後一同處理
3. 時間複雜度為 nlogn -> n 層 * logN (執行次數)
4. 合併的實現邏輯是：
a. 兩陣列各自的 index 從 0 開始互比，若有滿足條件則該 index 加 1 ，直到任何一方 index 超過長度為止
b. 由於你不會知道各自的陣列 index 哪一個已走完全部，所以兩個陣列都需要跑一次迴圈將剩餘的跑完
5. 無論原始陣列是否已經排序完成，都需要完整跑完一次。因此無論何種情況的時間複雜度都是 nlogN
2. divide & conquer – 拆成重複的小塊累積 (遞迴)，然後一同處理
3. 時間複雜度為 nlogn -> n 層 * logN (執行次數)
4. 合併的實現邏輯是：
a. 兩陣列各自的 index 從 0 開始互比，若有滿足條件則該 index 加 1 ，直到任何一方 index 超過長度為止
b. 由於你不會知道各自的陣列 index 哪一個已走完全部，所以兩個陣列都需要跑一次迴圈將剩餘的跑完
5. 無論原始陣列是否已經排序完成，都需要完整跑完一次。因此無論何種情況的時間複雜度都是 nlogN
