|
| 1 | +#JavaScript 演算法與資料結構 |
| 2 | + |
| 3 | +[](https://travis-ci.org/trekhleb/javascript-algorithms) |
| 4 | +[](https://codecov.io/gh/trekhleb/javascript-algorithms) |
| 5 | + |
| 6 | +這個知識庫包含許多 JavaScript 的資料結構與演算法的基礎範例。 |
| 7 | +每個演算法和資料結構都有其個別的文件，內有相關的解釋以及更多相關的文章或Youtube影片連結。 |
| 8 | + |
| 9 | +_Read this in other languages:_[简体中文](https://github.com/trekhleb/javascript-algorithms/blob/master/README.zh-CN.md) |
| 10 | + |
| 11 | +_Read this in other languages:_[繁體中文](https://github.com/trekhleb/javascript-algorithms/blob/master/README.zh-TW.md) |
| 12 | + |
| 13 | +##資料結構 |
| 14 | + |
| 15 | +資料結構是一個電腦用來組織和排序資料的特定方式，透過這樣的方式資料可以有效率地被讀取以及修改。更精確地說，一個資料結構是一個資料值的集合、彼此間的關係，函數或者運作可以應用於資料上。 |
| 16 | + |
| 17 | +*[Linked List 鏈結串列](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/linked-list) |
| 18 | +*[Queue 貯列](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/queue) |
| 19 | +*[Stack 堆疊](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/stack) |
| 20 | +*[Hash Table 雜湊表](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/hash-table) |
| 21 | +*[Heap 堆](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/heap) |
| 22 | +*[Priority Queue 優先貯列](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/priority-queue) |
| 23 | +*[Trie 字典樹](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/trie) |
| 24 | +*[Tree 樹](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/tree) |
| 25 | +*[Binary Search Tree 二元搜尋樹](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/tree/binary-search-tree) |
| 26 | +*[AVL Tree AVL樹](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/tree/avl-tree) |
| 27 | +* Red-Black Tree |
| 28 | +* Suffix Tree |
| 29 | +* Segment Tree or Interval Tree |
| 30 | +* Binary Indexed Tree or Fenwick Tree |
| 31 | +*[Graph 圖](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/graph) (both directed and undirected) |
| 32 | +*[Disjoint Set 互斥集](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/disjoint-set) |
| 33 | + |
| 34 | +##演算法 |
| 35 | + |
| 36 | +演算法是一個如何解決一類問題的非模糊規格。演算法是一個具有精確地定義了一系列運作的規則的集合 |
| 37 | + |
| 38 | +###演算法議題分類 TODO |
| 39 | + |
| 40 | +***數學類** |
| 41 | +*[Factorial](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/factorial) |
| 42 | +*[Fibonacci Number](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/fibonacci) |
| 43 | +*[Primality Test](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/primality-test) (trial division method) |
| 44 | +*[Euclidean Algorithm](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/euclidean-algorithm) - calculate the Greatest Common Divisor (GCD) |
| 45 | +*[Least Common Multiple](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/least-common-multiple) (LCM) |
| 46 | +*[Integer Partition](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/integer-partition) |
| 47 | +***集合** |
| 48 | +*[Cartesian Product](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/cartesian-product) - product of multiple sets |
| 49 | +*[Power Set](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/power-set) - all subsets of the set |
| 50 | +*[Permutations](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/permutations) (with and without repetitions) |
| 51 | +*[Combinations](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/combinations) (with and without repetitions) |
| 52 | +*[Fisher–Yates Shuffle](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/fisher-yates) - random permutation of a finite sequence |
| 53 | +*[Longest Common Subsequence](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/longest-common-subsequnce) (LCS) |
| 54 | +*[Longest Increasing subsequence](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/longest-increasing-subsequence) |
| 55 | +*[Shortest Common Supersequence](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/shortest-common-supersequence) (SCS) |
| 56 | +*[Knapsack Problem](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/knapsack-problem) - "0/1" and "Unbound" ones |
| 57 | +*[Maximum Subarray](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/maximum-subarray) - "Brute Force" and "Dynamic Programming" (Kadane's) versions |
| 58 | +***字串** |
| 59 | +*[Levenshtein Distance](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/levenshtein-distance) - minimum edit distance between two sequences |
| 60 | +*[Hamming Distance](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/hamming-distance) - number of positions at which the symbols are different |
| 61 | +*[Knuth–Morris–Pratt Algorithm](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/knuth-morris-pratt) - substring search |
| 62 | +*[Rabin Karp Algorithm](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/rabin-karp) - substring search |
| 63 | +*[Longest Common Substring](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/longest-common-substring) |
| 64 | +***搜尋** |
| 65 | +*[Binary Search](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/search/binary-search) |
| 66 | +***排序** |
| 67 | +*[Bubble Sort](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/bubble-sort) |
| 68 | +*[Selection Sort](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/selection-sort) |
| 69 | +*[Insertion Sort](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/insertion-sort) |
| 70 | +*[Heap Sort](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/heap-sort) |
| 71 | +*[Merge Sort](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/merge-sort) |
| 72 | +*[Quicksort](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/quick-sort) |
| 73 | +*[Shellsort](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/shell-sort) |
| 74 | +***樹** |
| 75 | +*[Depth-First Search](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/tree/depth-first-search) (DFS) |
| 76 | +*[Breadth-First Search](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/tree/breadth-first-search) (BFS) |
| 77 | +***圖** |
| 78 | +*[Depth-First Search](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/depth-first-search) (DFS) |
| 79 | +*[Breadth-First Search](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/breadth-first-search) (BFS) |
| 80 | +*[Dijkstra Algorithm](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/dijkstra) - finding shortest path to all graph vertices |
| 81 | +*[Bellman-Ford Algorithm](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/bellman-ford) - finding shortest path to all graph vertices |
| 82 | +*[Detect Cycle](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/detect-cycle) - for both directed and undirected graphs (DFS and Disjoint Set based versions) |
| 83 | +*[Prim’s Algorithm](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/prim) - finding Minimum Spanning Tree (MST) for weighted undirected graph |
| 84 | +*[Kruskal’s Algorithm](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/kruskal) - finding Minimum Spanning Tree (MST) for weighted undirected graph |
| 85 | +*[Topological Sorting](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/topological-sorting) - DFS method |
| 86 | +*[Articulation Points](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/articulation-points) - Tarjan's algorithm (DFS based) |
| 87 | +*[Bridges](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/bridges) - DFS based algorithm |
| 88 | +*[Eulerian Path and Eulerian Circuit](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/eulerian-path) - Fleury's algorithm - Visit every edge exactly once |
| 89 | +*[Hamiltonian Cycle](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/hamiltonian-cycle) - Visit every vertex exactly once |
| 90 | +*[Strongly Connected Components](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/strongly-connected-components) - Kosaraju's algorithm |
| 91 | +*[Travelling Salesman Problem](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/travelling-salesman) - shortest possible route that visits each city and returns to the origin city |
| 92 | +***未分類** |
| 93 | +*[Tower of Hanoi](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/uncategorized/hanoi-tower) |
| 94 | +*[N-Queens Problem](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/uncategorized/n-queens) |
| 95 | +*[Knight's Tour](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/uncategorized/knight-tour) |
| 96 | + |
| 97 | +###Algorithms by Paradigm |
| 98 | + |
| 99 | +An algorithmic paradigm is a generic method or approach which underlies the design of a class |
| 100 | +of algorithms. It is an abstraction higher than the notion of an algorithm, just as an |
| 101 | +algorithm is an abstraction higher than a computer program. |
| 102 | + |
| 103 | +***Brute Force** - look at all the possibilities and selects the best solution |
| 104 | +*[Maximum Subarray](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/maximum-subarray) |
| 105 | +*[Travelling Salesman Problem](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/travelling-salesman) - shortest possible route that visits each city and returns to the origin city |
| 106 | +***Greedy** - choose the best option at the current time, without any consideration for the future |
| 107 | +*[Unbound Knapsack Problem](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/knapsack-problem) |
| 108 | +*[Dijkstra Algorithm](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/dijkstra) - finding shortest path to all graph vertices |
| 109 | +*[Prim’s Algorithm](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/prim) - finding Minimum Spanning Tree (MST) for weighted undirected graph |
| 110 | +*[Kruskal’s Algorithm](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/kruskal) - finding Minimum Spanning Tree (MST) for weighted undirected graph |
| 111 | +***Divide and Conquer** - divide the problem into smaller parts and then solve those parts |
| 112 | +*[Binary Search](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/search/binary-search) |
| 113 | +*[Tower of Hanoi](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/uncategorized/hanoi-tower) |
| 114 | +*[Euclidean Algorithm](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/euclidean-algorithm) - calculate the Greatest Common Divisor (GCD) |
| 115 | +*[Permutations](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/permutations) (with and without repetitions) |
| 116 | +*[Combinations](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/combinations) (with and without repetitions) |
| 117 | +*[Merge Sort](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/merge-sort) |
| 118 | +*[Quicksort](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/quick-sort) |
| 119 | +*[Tree Depth-First Search](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/tree/depth-first-search) (DFS) |
| 120 | +*[Graph Depth-First Search](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/depth-first-search) (DFS) |
| 121 | +***Dynamic Programming** - build up to a solution using previously found sub-solutions |
| 122 | +*[Fibonacci Number](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/fibonacci) |
| 123 | +*[Levenshtein Distance](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/levenshtein-distance) - minimum edit distance between two sequences |
| 124 | +*[Longest Common Subsequence](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/longest-common-subsequnce) (LCS) |
| 125 | +*[Longest Common Substring](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/longest-common-substring) |
| 126 | +*[Longest Increasing subsequence](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/longest-increasing-subsequence) |
| 127 | +*[Shortest Common Supersequence](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/shortest-common-supersequence) |
| 128 | +*[0/1 Knapsack Problem](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/knapsack-problem) |
| 129 | +*[Integer Partition](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/integer-partition) |
| 130 | +*[Maximum Subarray](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/maximum-subarray) |
| 131 | +*[Bellman-Ford Algorithm](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/bellman-ford) - finding shortest path to all graph vertices |
| 132 | +***Backtracking** - similarly to brute force try to generate all possible solutions but each time you generate a solution test |
| 133 | +if it satisfies all conditions, and only then continue generating subsequent solutions. Otherwise backtrack and go on a |
| 134 | +different path of finding solution |
| 135 | +*[Hamiltonian Cycle](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/hamiltonian-cycle) - Visit every vertex exactly once |
| 136 | +*[N-Queens Problem](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/uncategorized/n-queens) |
| 137 | +*[Knight's Tour](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/uncategorized/knight-tour) |
| 138 | +***Branch & Bound** |
| 139 | + |
| 140 | +##如何使用本知識庫 |
| 141 | + |
| 142 | +**安裝所有必須套件** |
| 143 | + |
| 144 | +``` |
| 145 | +npm install |
| 146 | +``` |
| 147 | + |
| 148 | +**執行所有測試** |
| 149 | +``` |
| 150 | +npm test |
| 151 | +``` |
| 152 | + |
| 153 | +**以名稱執行該測試** |
| 154 | +``` |
| 155 | +npm test -- -t 'LinkedList' |
| 156 | +``` |
| 157 | +**Playground** |
| 158 | + |
| 159 | +You may play with data-structures and algorithms in`./src/playground/playground.js` file and write |
| 160 | +tests for it in`./src/playground/__test__/playground.test.js`. |
| 161 | + |
| 162 | +Then just simply run the following command to test if your playground code works as expected: |
| 163 | + |
| 164 | +``` |
| 165 | +npm test -- -t 'playground' |
| 166 | +``` |
| 167 | + |
| 168 | +##有用的資訊 |
| 169 | + |
| 170 | +###參考 |
| 171 | + |
| 172 | +[▶ Data Structures and Algorithms on YouTube](https://www.youtube.com/playlist?list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8) |
| 173 | + |
| 174 | +###大 O 標記 |
| 175 | + |
| 176 | +Order of growth of algorithms specified in Big O notation. |
| 177 | + |
| 178 | + |
| 179 | + |
| 180 | +資料來源:[Big O Cheat Sheet](http://bigocheatsheet.com/). |
| 181 | + |
| 182 | +Below is the list of some of the most used Big O notations and their performance comparisons against different sizes of the input data. |
| 183 | + |
| 184 | +| Big O Notation| Computations for 10 elements| Computations for 100 elements| Computations for 1000 elements| |
| 185 | +| --------------| ----------------------------| -----------------------------| -------------------------------| |
| 186 | +|**O(1)**| 1| 1| 1| |
| 187 | +|**O(log N)**| 3| 6| 9| |
| 188 | +|**O(N)**| 10| 100| 1000| |
| 189 | +|**O(N log N)**| 30| 600| 9000| |
| 190 | +|**O(N^2)**| 100| 10000| 1000000| |
| 191 | +|**O(2^N)**| 1024| 1.26e+29| 1.07e+301| |
| 192 | +|**O(N!)**| 3628800| 9.3e+157| 4.02e+2567| |
| 193 | + |
| 194 | +###Data Structure Operations Complexity |
| 195 | +
|
| 196 | +| Data Structure| Access| Search| Insertion| Deletion| |
| 197 | +| -----------------------| :-------:| :-------:| :-------:| :-------:| |
| 198 | +|**Array**| 1| n| n| n| |
| 199 | +|**Stack**| n| n| 1| 1| |
| 200 | +|**Queue**| n| n| 1| 1| |
| 201 | +|**Linked List**| n| n| 1| 1| |
| 202 | +|**Hash Table**| -| n| n| n| |
| 203 | +|**Binary Search Tree**| n| n| n| n| |
| 204 | +|**B-Tree**| log(n)| log(n)| log(n)| log(n)| |
| 205 | +|**Red-Black Tree**| log(n)| log(n)| log(n)| log(n)| |
| 206 | +|**AVL Tree**| log(n)| log(n)| log(n)| log(n)| |
| 207 | + |
| 208 | +###Array Sorting Algorithms Complexity |
| 209 | + |
| 210 | +| Name| Best| Average| Worst| Memory| Stable| |
| 211 | +| ---------------------| :-------:| :-------:| :-----------:| :-------:| :-------:| |
| 212 | +|**Bubble sort**| n| n^2| n^2| 1| Yes| |
| 213 | +|**Insertion sort**| n| n^2| n^2| 1| Yes| |
| 214 | +|**Selection sort**| n^2| n^2| n^2| 1| No| |
| 215 | +|**Heap sort**| n log(n)| n log(n)| n log(n)| 1| No| |
| 216 | +|**Merge sort**| n log(n)| n log(n)| n log(n)| n| Yes| |
| 217 | +|**Quick sort**| n log(n)| n log(n)| n^2| log(n)| No| |
| 218 | +|**Shell sort**| n log(n)| depends on gap sequence| n (log(n))^2| 1| No| |