[筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 11

重念一次早該補起來的「資料結構與演算法」。這篇筆記來初步簡介一下 合併演算法

notes-theideaofalgorithm-javascript-1


課程相關資訊

[連結]: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

程式碼

https://github.com/andy922200/hiskio-the-idea-of-algorithm/commit/bdd7b79afd5a69e252b052047f5098e6fcd3dd84


系列文章

  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 9
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 8
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 7
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 6
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 5
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 4
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 3
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 2
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 15
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 14
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 13
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 12
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 10
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 1
  • 按讚加入粉絲團

    延伸閱讀