javascript-algorithms

JavaScript 演算法與資料結構

CI codecov

這個知識庫包含許多 JavaScript 的資料結構與演算法的基礎範例。 每個演算法和資料結構都有其個別的文件,內有相關的解釋以及更多相關的文章或Youtube影片連結。

Read this in other languages: English, 简体中文, 한국어, 日本語, Polski, Français, Español, Português, Русский, Türk, Italiana

資料結構

資料結構是一個電腦用來組織和排序資料的特定方式,透過這樣的方式資料可以有效率地被讀取以及修改。更精確地說,一個資料結構是一個資料值的集合、彼此間的關係,函數或者運作可以應用於資料上。

演算法

演算法是一個如何解決一類問題的非模糊規格。演算法是一個具有精確地定義了一系列運作的規則的集合

演算法議題分類

演算法範型

演算法的範型是一個泛用方法或設計一類底層演算法的方式。它是一個比演算法的概念更高階的抽象化,就像是演算法是比電腦程式更高階的抽象化。

如何使用本知識庫

安裝所有必須套件

npm install

執行所有測試

npm test

以名稱執行該測試

npm test -- 'LinkedList'

練習場

你可以透過在./src/playground/playground.js裡面的檔案練習資料結構以及演算法,並且撰寫在./src/playground/__test__/playground.test.js裡面的測試程式。

接著直接執行下列的指令來測試你練習的 code 是否如預期運作:

npm test -- 'playground'

有用的資訊

參考

▶ Data Structures and Algorithms on YouTube

大 O 標記

特別用大 O 標記演算法增長度的排序。

Big O 表

資料來源: Big O Cheat Sheet.

下列列出幾個常用的 Big O 標記以及其不同大小資料量輸入後的運算效能比較。

Big O 標記 10個資料量需花費的時間 100個資料量需花費的時間 1000個資料量需花費的時間
O(1) 1 1 1
O(log N) 3 6 9
O(N) 10 100 1000
O(N log N) 30 600 9000
O(N^2) 100 10000 1000000
O(2^N) 1024 1.26e+29 1.07e+301
O(N!) 3628800 9.3e+157 4.02e+2567

資料結構運作複雜度

資料結構 存取 搜尋 插入 刪除
陣列 1 n n n
堆疊 n n 1 1
貯列 n n 1 1
鏈結串列 n n 1 1
雜湊表 - n n n
二元搜尋樹 n n n n
B-Tree log(n) log(n) log(n) log(n)
紅黑樹 log(n) log(n) log(n) log(n)
AVL Tree log(n) log(n) log(n) log(n)

陣列排序演算法複雜度

名稱 最佳 平均 最差 記憶體 穩定
氣派排序 n n^2 n^2 1 Yes
插入排序 n n^2 n^2 1 Yes
選擇排序 n^2 n^2 n^2 1 No
Heap 排序 n log(n) n log(n) n log(n) 1 No
合併排序 n log(n) n log(n) n log(n) n Yes
快速排序 n log(n) n log(n) n^2 log(n) No
希爾排序 n log(n) 由gap sequence決定 n (log(n))^2 1 No