Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commite26e986

Browse files
kj-huangtrekhleb
authored andcommitted
Finish main part of translation (trekhleb#18)
* add chinese overview* translate* add* translate english
1 parentc6aa8ab commite26e986

File tree

2 files changed

+212
-0
lines changed

2 files changed

+212
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -11,6 +11,7 @@ with related explanations and links for further reading and YouTube
1111
videos.
1212

1313
_Read this in other languages:_[简体中文](https://github.com/trekhleb/javascript-algorithms/blob/master/README.zh-CN.md)
14+
_Read this in Traditional Chinese:_[繁體中文](https://github.com/trekhleb/javascript-algorithms/blob/master/README.zh-TW.md)
1415

1516
##Data Structures
1617

‎Readme.zh-TW.md

Lines changed: 211 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,211 @@
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+
##資料結構
12+
13+
資料結構是一個電腦用來組織和排序資料的特定方式，透過這樣的方式資料可以有效率地被讀取以及修改。更精確地說，一個資料結構是一個資料值的集合、彼此間的關係，函數或者運作可以應用於資料上。
14+
15+
*[Linked List 鏈結串列](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/linked-list)
16+
*[Queue 貯列](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/queue)
17+
*[Stack 堆疊](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/stack)
18+
*[Hash Table 雜湊表](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/hash-table)
19+
*[Heap 堆](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/heap)
20+
*[Priority Queue 優先貯列](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/priority-queue)
21+
*[Trie 字典樹](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/trie)
22+
*[Tree 樹](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/tree)
23+
*[Binary Search Tree 二元搜尋樹](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/tree/binary-search-tree)
24+
*[AVL Tree AVL樹](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/tree/avl-tree)
25+
* 紅黑樹
26+
* 後綴樹
27+
* 線段樹 或 間隔樹
28+
* 樹狀數組或二叉索引樹
29+
*[Graph 圖](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/graph) (有向跟無向皆包含)
30+
*[Disjoint Set 互斥集](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/disjoint-set)
31+
32+
##演算法
33+
34+
演算法是一個如何解決一類問題的非模糊規格。演算法是一個具有精確地定義了一系列運作的規則的集合
35+
36+
###演算法議題分類
37+
38+
***數學類**
39+
*[階層](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/factorial)
40+
*[費伯納西數列](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/fibonacci)
41+
*[Primality Test](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/primality-test) (排除法)
42+
*[歐幾里得算法](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/euclidean-algorithm) - 計算最大公因數 (GCD)
43+
*[最小公倍數](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/least-common-multiple) (LCM)
44+
*[整數拆分](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/integer-partition)
45+
***集合**
46+
*[笛卡爾積](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/cartesian-product) - 多個集合的乘積
47+
*[冪集合](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/power-set) - 所有集合的子集合
48+
*[排列](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/permutations) (有/無重複)
49+
*[组合](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/combinations) (有/無重複)
50+
*[洗牌算法](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/fisher-yates) - 隨機置換一有限序列
51+
*[最長共同子序列](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/longest-common-subsequnce) (LCS)
52+
*[最長遞增子序列](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/longest-increasing-subsequence)
53+
*[Shortest Common Supersequence](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/shortest-common-supersequence) (SCS)
54+
*[背包問題](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/knapsack-problem) - "0/1" and "Unbound" ones
55+
*[最大子序列問題](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/maximum-subarray) - 暴力法以及動態編程的(Kadane's)版本
56+
***字串**
57+
*[萊文斯坦距離](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/levenshtein-distance) - 兩序列間的最小編輯距離
58+
*[漢明距離](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/hamming-distance) - number of positions at which the symbols are different
59+
*[KMP 演算法](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/knuth-morris-pratt) - 子字串搜尋
60+
*[Rabin Karp 演算法](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/rabin-karp) - 子字串搜尋
61+
*[最長共通子序列](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/longest-common-substring)
62+
***搜尋**
63+
*[二元搜尋](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/search/binary-search)
64+
***排序**
65+
*[氣泡排序](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/bubble-sort)
66+
*[選擇排序](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/selection-sort)
67+
*[插入排序](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/insertion-sort)
68+
*[堆排序](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/heap-sort)
69+
*[合併排序](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/merge-sort)
70+
*[快速排序](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/quick-sort)
71+
*[希爾排序](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/shell-sort)
72+
***樹**
73+
*[深度優先搜尋](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/tree/depth-first-search) (DFS)
74+
*[廣度優先搜尋](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/tree/breadth-first-search) (BFS)
75+
***圖**
76+
*[深度優先搜尋](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/depth-first-search) (DFS)
77+
*[廣度優先搜尋](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/breadth-first-search) (BFS)
78+
*[Dijkstra 演算法](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/dijkstra) - 找到所有圖頂點的最短路徑
79+
*[Bellman-Ford 演算法](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/bellman-ford) - 找到所有圖頂點的最短路徑
80+
*[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)
81+
*[Prim’s 演算法](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/prim) - finding Minimum Spanning Tree (MST) for weighted undirected graph
82+
*[Kruskal’s 演算法](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/kruskal) - finding Minimum Spanning Tree (MST) for weighted undirected graph
83+
*[拓撲排序](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/topological-sorting) - DFS method
84+
*[關節點](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/articulation-points) - Tarjan's algorithm (DFS based)
85+
*[橋](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/bridges) - DFS based algorithm
86+
*[尤拉路徑及尤拉環](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/eulerian-path) - Fleury's algorithm - Visit every edge exactly once
87+
*[漢彌爾頓環](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/hamiltonian-cycle) - Visit every vertex exactly once
88+
*[強連通組件](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/strongly-connected-components) - Kosaraju's algorithm
89+
*[旅行推銷員問題](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
90+
***未分類**
91+
*[河內塔](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/uncategorized/hanoi-tower)
92+
*[N-皇后問題](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/uncategorized/n-queens)
93+
*[騎士走棋盤](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/uncategorized/knight-tour)
94+
95+
###演算法範型
96+
97+
演算法的範型是一個泛用方法或設計一類底層演算法的方式。它是一個比演算法的概念更高階的抽象化，就像是演算法是比電腦程式更高階的抽象化。
98+
99+
***暴力法** - 尋遍所有的可能解然後選取最好的解
100+
*[最大子序列](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/maximum-subarray)
101+
*[旅行推銷員問題](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
102+
***貪婪法** - choose the best option at the current time, without any consideration for the future
103+
*[未定背包問題](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/knapsack-problem)
104+
*[Dijkstra 演算法](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/dijkstra) - 找到所有圖頂點的最短路徑
105+
*[Prim’s 演算法](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/prim) - finding Minimum Spanning Tree (MST) for weighted undirected graph
106+
*[Kruskal’s 演算法](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/kruskal) - finding Minimum Spanning Tree (MST) for weighted undirected graph
107+
***分治法** - divide the problem into smaller parts and then solve those parts
108+
*[二元搜尋](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/search/binary-search)
109+
*[河內塔](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/uncategorized/hanoi-tower)
110+
*[歐幾里得演算法](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/euclidean-algorithm) - calculate the Greatest Common Divisor (GCD)
111+
*[排列](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/permutations) (有/無重複)
112+
*[组合](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/combinations) (有/無重複)
113+
*[合併排序](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/merge-sort)
114+
*[快速排序](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/quick-sort)
115+
*[樹深度優先搜尋](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/tree/depth-first-search) (DFS)
116+
*[圖深度優先搜尋](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/depth-first-search) (DFS)
117+
***動態編程** - build up to a solution using previously found sub-solutions
118+
*[費伯納西數列](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/fibonacci)
119+
*[萊溫斯坦距離](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/levenshtein-distance) - minimum edit distance between two sequences
120+
*[最長共同子序列](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/longest-common-subsequnce) (LCS)
121+
*[最長共同子字串](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/longest-common-substring)
122+
*[最長遞增子序列](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/longest-increasing-subsequence)
123+
*[最短共同子序列](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/shortest-common-supersequence)
124+
*[0/1背包問題](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/knapsack-problem)
125+
*[整數拆分](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/integer-partition)
126+
*[最大子序列](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/maximum-subarray)
127+
*[Bellman-Ford 演算法](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/bellman-ford) - finding shortest path to all graph vertices
128+
***回溯法** - 用類似暴力法來嘗試產生所有可能解，但每次只在能滿足所有測試條件，且只有繼續產生子序列方案來產生的解決方案。否則回溯並尋找不同路徑的解決方案。
129+
*[漢彌爾頓迴路](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/hamiltonian-cycle) - Visit every vertex exactly once
130+
*[N-皇后問題](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/uncategorized/n-queens)
131+
*[騎士走棋盤](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/uncategorized/knight-tour)
132+
***Branch & Bound**
133+
134+
##如何使用本知識庫
135+
136+
**安裝所有必須套件**
137+
138+
```
139+
npm install
140+
```
141+
142+
**執行所有測試**
143+
```
144+
npm test
145+
```
146+
147+
**以名稱執行該測試**
148+
```
149+
npm test -- -t 'LinkedList'
150+
```
151+
**練習場**
152+
153+
你可以透過在`./src/playground/playground.js`裡面的檔案練習資料結構以及演算法，並且撰寫在`./src/playground/__test__/playground.test.js`裡面的測試程式。
154+
155+
接著直接執行下列的指令來測試你練習的 code 是否如預期運作：
156+
157+
```
158+
npm test -- -t 'playground'
159+
```
160+
161+
##有用的資訊
162+
163+
###參考
164+
165+
[▶ Data Structures and Algorithms on YouTube](https://www.youtube.com/playlist?list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8)
166+
167+
###大 O 標記
168+
169+
特別用大 O 標記演算法增長度的排序。
170+
171+
![Big O 表](https://github.com/trekhleb/javascript-algorithms/blob/master/assets/big-o-graph.png?raw=true)
172+
173+
資料來源:[Big O Cheat Sheet](http://bigocheatsheet.com/).
174+
175+
下列列出幾個常用的 Big O 標記以及其不同大小資料量輸入後的運算效能比較。
176+
177+
| Big O 標記| 10個資料量需花費的時間| 100個資料量需花費的時間| 1000個資料量需花費的時間|
178+
| --------------| ----------------------------| -----------------------------| -------------------------------|
179+
|**O(1)**| 1| 1| 1|
180+
|**O(log N)**| 3| 6| 9|
181+
|**O(N)**| 10| 100| 1000|
182+
|**O(N log N)**| 30| 600| 9000|
183+
|**O(N^2)**| 100| 10000| 1000000|
184+
|**O(2^N)**| 1024| 1.26e+29| 1.07e+301|
185+
|**O(N!)**| 3628800| 9.3e+157| 4.02e+2567|
186+
187+
###資料結構運作複雜度
188+
189+
| 資料結構| 存取| 搜尋| 插入| 刪除|
190+
| -----------------------| :-------:| :-------:| :-------:| :-------:|
191+
|**陣列**| 1| n| n| n|
192+
|**堆疊**| n| n| 1| 1|
193+
|**貯列**| n| n| 1| 1|
194+
|**鏈結串列**| n| n| 1| 1|
195+
|**雜湊表**| -| n| n| n|
196+
|**二元搜尋樹**| n| n| n| n|
197+
|**B-Tree**| log(n)| log(n)| log(n)| log(n)|
198+
|**紅黑樹**| log(n)| log(n)| log(n)| log(n)|
199+
|**AVL Tree**| log(n)| log(n)| log(n)| log(n)|
200+
201+
###陣列搜尋演算法複雜度
202+
203+
| 名稱| 最佳| 平均| 最差| 記憶體| 穩定|
204+
| ---------------------| :-------:| :-------:| :-----------:| :-------:| :-------:|
205+
|**氣派排序**| n| n^2| n^2| 1| Yes|
206+
|**插入排序**| n| n^2| n^2| 1| Yes|
207+
|**選擇排序**| n^2| n^2| n^2| 1| No|
208+
|**Heap 排序**| n log(n)| n log(n)| n log(n)| 1| No|
209+
|**合併排序**| n log(n)| n log(n)| n log(n)| n| Yes|
210+
|**快速排序**| n log(n)| n log(n)| n^2| log(n)| No|
211+
|**希爾排序**| n log(n)| 由gap sequence決定| n (log(n))^2| 1| No|

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp