Skip to content

Commit 2364de7

Browse files
kj-huangtrekhleb
kj-huang
authored and
trekhleb
committed
add chinese overview (trekhleb#17)
1 parent e10ea04 commit 2364de7

File tree

1 file changed

+218
-0
lines changed

1 file changed

+218
-0
lines changed

‎Readme.zh-TW.md

+218
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,218 @@
1+
# JavaScript 演算法與資料結構
2+
3+
[![build status](https://travis-ci.org/trekhleb/javascript-algorithms.svg?branch=master)](https://travis-ci.org/trekhleb/javascript-algorithms)
4+
[![codecov](https://codecov.io/gh/trekhleb/javascript-algorithms/branch/master/graph/badge.svg)](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+
![Big O 表](https://github.com/trekhleb/javascript-algorithms/blob/master/assets/big-o-graph.png?raw=true)
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 |

0 commit comments

Comments
 (0)