JavaScript Thuật Toán và Cấu Trúc Dữ Liệu

Repository này bao gồm nhiều ví dụ thuật toán và cấu trúc dữ liệu phổ biến dựa trên Javascript.

Mối thuật toán và cấu trúc dữ liệu có README riêng với những lý giải và links liên quan để đọc thêm (bao gồm cả những videos trên Youtube).

Đọc bằng ngôn ngữ khác: English, 简体中文, 繁體中文, 한국어, 日本語, Polski, Français, Español, Português, Русский, Türk, Italiana, Bahasa Indonesia, Українська, Arabic

☝ Dự án này chỉ được sử dụng cho mục đích học tập và nghiên cứu, không được dùng cho mục đích thương mại.

Cấu Trúc Dữ Liệu

Cấu trúc dữ liệu là một cách cụ thể để tổ chức và lưu trữ dữ liệu trong máy tính để nó có thể được truy cập và sửa đổi một cách hiệu quả. Chính xác hơn, cấu trúc dữ liệu là một tập hợp các giá trị dữ liệu, các mối quan hệ giữa chúng và các hàm hoặc phép toán có thể được áp dụng cho dữ liệu.

B - Cơ bản, A - Nâng cao

B Danh sách liên kết
B Danh sách liên kết đôi
B Hàng đợi
B Ngăn xếp
B Bảng băm
B Đống - max và min heap
B Hàng đợi ưu tiên
A Cây tiền tố
A Cây
A Cây tìm kiếm nhị phân
A Cây AVL
A Cây đỏ đen
A Cây phân đoạn - với các ví dụ truy vấn phạm vi nhỏ nhất/lớn nhất/tổng
A CÂy Fenwick (Cây chỉ mục nhị phân)
A Đồ thị (có hướng và vô hướng)
A Tập hợp không giao nhau
A Bộ lọc Bloom

Thuật Toán

Thuật toán là một đặc tả rõ ràng về cách giải quyết một lớp vấn đề. Nó là một tập hợp các quy tắc xác định chính xác một chuỗi phép toán.

B - Cơ bản, A - Nâng cao

Thuật toán theo chủ đề

Toán
B Thao tác bit - đặt/lấy/cập nhật/xóa bit, nhân/chia 2, đổi dấu âm,...
B Giai thừa
B Số Fibonacci - cổ điển và dạng đóng
B Thừa số nguyên tố - tìm và đếm thừa số nguyên tố sử dụng định luật Hardy-Ramanujan's
B Kiểm tra tính nguyên tố (phân chia thử nghiệm)
B Thuật toán Euclid - tính ước số chung lớn nhất (GCD)
B Bội số chung nhỏ nhất (LCM)
B Sàng số nguyên tố - tìm tất cả các số nguyên tố trong bất kỳ phạm vi nhất định nào
B Xác định lũy thừa của 2 - kiểm tra xem số có phải là lũy thừa của 2 hay không (thuật toán nguyên bản và theo bit)
B Tam giác Pascal
B Số phức - số phức và các phép toán cơ bản với số phức
B Radian & độ - chuyển đổi giữa đơn vị radian và độ
B Tính nhanh lũy thừa
B Phương pháp Horner's - tính giá trị đa thức
B Ma trận - ma trận và các phép toán cơ bản (phép nhân, phép chuyển vị,...)
B Khoảng cách Euclid - khoảng cách giữa hai điểm/véc-tơ/ma trận
A Phân hoạch
A Căn bậc hai - phương pháp Newton
A Thuật cắt đường tròn - Lưu Huy - phép tính gần đúng số π dựa vào đa giác
A Biến đổi Fourier rời rạc - phân giải tín hiệu thời gian thành các tần số tạo nên tín hiệu đó
Tập hợp
B Tích Đề-các - tích của nhiều tập hợp
B Thuật toán xáo trộn - dãy hữu hạn hoán vị ngẫu nhiên
A Tập lũy thừa - tập hợp chứa tất cả các tập con (theo bit và quay lui)
A Hoán vị (lặp và không lặp)
A Tổ hợp (lặp và không lặp)
A Dãy con chung dài nhất (LCS)
A Dãy con chung tăng dần dài nhất
A Dãy con chung ngắn nhất (SCS)
A Bài toán xếp ba lô - dạng 0-1 và không bị chặn
A Mảng con lớn nhất - phiên bản vét cạn và quy hoạch động (Kadane)
A Tổ hợp của tổng - tìm tất cả các tổ hợp tạo thành tổng cụ thể
Chuỗi
B Khoảng cách Hamming - số các vị trí các ký hiệu khác nhau
A Khoảng cách Levenshtein - khoảng cách thay đổi nhỏ nhất giữa hai chuỗi ký tự
A Thuật toán Knuth–Morris–Pratt (thuật toán KMP) - tìm chuỗi con (đối sánh mẫu)
A Thuật toán Z - tìm chuỗi con (đối sánh mẫu)
A Thuật toán Rabin Karp - tìm chuỗi con
A Xâu con chung dài nhất
A Phối biểu thức chính quy
Tìm kiếm
B Tìm kiếm tuyến tính
B Tìm kiếm nhảy (tìm khối) - tìm kiếm trong mảng đã sắp xếp
B Tìm kiếm nhị phân - tìm kiếm trong mảng đã sắp xếp
B Tìm kiếm nội suy - Tìm kiếm strong mảng có thứ tự được phân phối đồng nhất
Sắp xếp
B Sắp xếp nổi bọt
B Sắp xếp chọn
B Sắp xếp chèn
B Sắp xếp vun đống
B Sắp xếp trộn
B Sắp xếp nhanh - Tại chỗ và không tại chỗ
B Shellsort
B Sắp xếp đếm
B Sắp xếp theo cơ số
Danh sách liên kết
B Di chuyển chính hướng
B Di chuyển ngược hướng
Cây
B Depth-First Search (DFS)
B Breadth-First Search (BFS)
Đồ thị
B Tìm kiếm theo chiều sâu (DFS)
B Tìm kiếm theo chiều rộng (BFS)
B Thuật toán Kruskal - tìm cây bao trùm nhỏ nhất (MST) cho đồ thị vô hướng có trọng số
A Thuật toán Dijkstra Algorithm - tìm những đường ngắn nhất từ một định tới tất cả các đỉnh
A Thuật toán Bellman-Ford - tìm những đường ngắn nhất từ một đỉnh tới tất cả các đỉnh của đồ thị
A Thuật toán Floyd-Warshall - tìm những đường ngắn nhất giữa tất cả các cặp đỉnh
A Phát hiện vòng - cho cả đồ thị có hướng và vô hướng (dựa trên DFS và tập không giao)
A Thuật toán Prim - tìm cây bao trùm nhỏ nhất (MST) cho đồ thị vô hướng có trọng số
A Sắp xếp tô pô - phương pháp DFS
A Điểm khớp - Thuật toán Tarjan (dựa trên DFS)
A Cầu nối - dựa trên DFS
A Đường đi Euler và Chu trình Euler - thuật toán Fleury - đi qua các cạnh chỉ một lần duy nhất
A Chu trình Hamilton - đi qua các đỉnh chỉ một lần duy nhất
A Các thành phần kết nối chặt - Thuật toán Kosaraju
A Bài toán người bán hàng - tuyến đường ngắn nhất có thể đến thăm từng thành phố và trở về thành phố gốc
Mật mã học
B Băm đa thức - lăn hàm băm dựa trên đa thức
B Mật mã hàng rào đường sắt - một thuật toán mật mã chuyển vị để mã hóa thông điệp
B Mật mã Caesar - mật mã chuyển vị đơn giản
B Mật mã Hill - mật mã chuyển vị đơn giản dựa trên đại số tuyến tính
Học máy
B NanoNeuron - 7 hàm JS đơn giản minh họa cách máy tính thực sự có thể học (truyền thuận / truyền ngược)
B k-NN - thuật toán phân loại k láng giềng gần nhất
B k-Means - thuật toán phân cụm k-Means
Khác
B Tháp Hà Nội
B Xoay ma trận vuông - thuật toán tại chỗ
B Trò chơi nhảy - ví dụ quay lui, quy hoạch động (từ trên xuống + từ dưới lên), dynamic programming (top-down + bottom-up) và tham lam
B Các đường đi đặc trưng duy nhất - ví dụ quay lui, quy hoạch động và tam giác Pascal
B Thu thập nước mưa - bài toán bẫy nước mưa (phiên bản quy hoạch động và vét cạn)
B Cầu thang đệ quy - đếm số cách lên đến đỉnh (4 lời giải)
B Thời điểm tốt nhất để mua bán cổ phiếu - ví dụ chia để trị và một đường chuyền
A Bài toán n quân hậu
A Mã đi tuần

Thuật toán theo mẫu hình

Mẫu hình thuật toán là một phương pháp hoặc cách tiếp cận chung làm cơ sở cho việc thiết kế một lớp thuật toán. Nó là một sự trừu tượng cao hơn khái niệm về một thuật toán, cũng giống như một thuật toán là một sự trừu tượng cao hơn một chương trình máy tính.

Vét cạn - xem xét tất cả các khả năng và chọn giải pháp tốt nhất
B Tìm kiếm tuyến tính
B Thu thập nước mưa - bài toán bẫy nước mưa
B Cầu thang đệ quy - đếm số cách lên đến đỉnh
A Mảng con lớn nhất
A Bài toán người bán hàng - tuyến đường ngắn nhất có thể đến thăm từng thành phố và trở về thành phố gốc
A Biến đổi Fourier rời rạc - phân giải tín hiệu thời gian thành các tần số tạo nên tín hiệu đó
Tham lam - chọn phương án tốt nhất vào thời điểm hiện tại mà không cần cân nhắc đến tương lai
B Trò chơi nhảy
A Bài xếp ba lô không bị chặn
A Thuật toán Dijkstra - tìm những đường ngắn nhất từ một định tới tất cả các đỉnh
A Thuật toán Prim - tìm cây bao trùm nhỏ nhất (MST) cho đồ thị vô hướng có trọng số
A Thuật toán Kruskal - tìm cây bao trùm nhỏ nhất (MST) cho đồ thị vô hướng có trọng số
Chia để trị - chia vấn đề thành các phần nhỏ hơn rồi giải quyết các phần đó
B Tìm kiếm nhị phân
B Tháp Hà Nội
B Tam giác Pascal
B Thuật toán Euclid - tính ước số chung lớn nhất
B Sắp xếp trộn
B Sắp xếp nhanh
B Cây tìm kiếm theo chiều sâu (DFS)
B Đồ thị tìm kiếm theo chiều sâu (DFS)
B Ma trận - tạo và duyệt các ma trận có kích thước khác nhau
B Trò chơi nhảy
B Tính nhanh lũy thừa
B Thời điểm tốt nhất để mua bán cổ phiếu - ví dụ chia để trị và một đường chuyền
A Hoán vị (lặp và không lặp)
A Tổ hợp (lặp và không lặp)
Quy hoạch động - xây dựng một giải pháp bằng cách sử dụng các giải pháp phụ đã tìm thấy trước đây
B Số Fibonacci
B Trò chơi nhảy
B Đường đi độc nhất
B Thu thập nước mưa - bài toán bẫy nước mưa
B Cầu thang đệ quy - đếm số cách lên đến đỉnh
A Khoảng cách Levenshtein - khoảng cách thay đổi nhỏ nhất giữa hai chuỗi ký tự
A Dãy con chung dài nhất (LCS)
A Xâu con chung dài nhất
A Dãy con chung tăng dần dài nhất
A Dãy con chung ngắn nhất
A Bài xếp ba lô dạng 0-1
A Integer Partition
A Mảng con lớn nhất
A Thuật toán Bellman-Ford - tìm những đường ngắn nhất từ một đỉnh tới tất cả các đỉnh của đồ thị
A Thuật toán Floyd-Warshall - tìm những đường ngắn nhất giữa tất cả các cặp đỉnh
A Phối biểu thức chính quy
Quay lui - tương tự như vét cạn, cố tạo ra tất cả các giải pháp có thể, nhưng mỗi lần bạn tạo ra giải pháp tiếp theo, bạn sẽ kiểm tra xem nó có thỏa mãn tất cả các điều kiện hay không và chỉ khi thỏa mãn mới tiếp tục tạo ra các giải pháp tiếp theo. Nếu không, hãy quay lại và đi trên một con đường khác để tìm ra giải pháp. Thông thường, truyền DFS của không gian trạng thái được sử dụng.
B Trò chơi nhảy
B Đường đi độc nhất
B Tập lũy thừa - tập hợp chứa tất cả các tập con
A Chu trình Hamilton - đi qua các đỉnh một lần duy nhất
A Bài toán n quân hậu
A Mã đi tuần
A Tổ hợp của tổng - tìm tất cả các tổ hợp tạo thành tổng cụ thể
Branch & Bound - ghi nhớ giải pháp chi với phí thấp nhất được tìm thấy ở mỗi giai đoạn của quá trình tìm kiếm quay lui, sử dụng chi phí của giải pháp có chi phí thấp nhất được tìm thấy cho đến nay như một giới hạn dưới về chi phí của một giải pháp ít chi phí nhân cho bài toán, để loại bỏ các giải pháp từng phần với chi phí lớn hơn giải pháp chi phí thấp nhất được tìm thấy cho đến nay. Thông thường BFS duyệt kết hợp với duyệt DFS của cây không gian trạng thái đang được sử dụng.

Hướng dẫn sử dụng repository

Cài đặt tất cả các phụ thuộc

npm install

Chạy ESLint

Bạn có thể muốn chạy nó để kiểm tra chất lượng code.

npm run lint

Chạy tất cả các kiểm thử

npm test

Chạy kiểm thử theo tên

npm test -- 'LinkedList'

Sân chơi

Bạn có thể chơi với các cấu trúc dữ liệu và thuật toán trong tệp ./src/playground/playground.js và viết các bài kiểm thử cho nó ở ./src/playground/__test__/playground.test.js.

Sau đó, chỉ cần chạy lệnh sau để kiểm tra xem sân chơi của bạn có hoạt động như mong đợi hay không:

npm test -- 'playground'

Thông tin hữu ích

Tham khảo

▶ Data Structures and Algorithms on YouTube

Kí hiệu O lớn

Kí hiệu O lớn được dùng để phân loại thuật toán theo thời gian chạy hoặc yêu cầu không gian gia tăng khi kích thước đầu vào gia tăng. Trên biểu đồ bên dưới, bạn có thể tìm thấy hầu hết các thứ tự tăng trưởng phổ biến của các thuật toán được chỉ định trong ký hiệu O lớn.

Đồ thị O lớn

Nguồn: Big O Cheat Sheet.

Dưới đây là danh sách một số ký hiệu O lớn thông dụng và so sánh với các kích thước khác nhau của dữ liệu đầu vào.

Kí hiệu O lớn	Tính toán cho 10 phần tử	Tính toán cho 100 phần tử	Tính toán cho 1000 phần tử
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

Độ phức tạp của các phép toán cấu trúc dữ liệu

Cấu trúc dữ liệu	Truy cập	Tìm kiếm	Chèn	Xóa	Bình luận
Mảng	1	n	n	n
Ngăn xếp	n	n	1	1
Hàng đợi	n	n	1	1
Danh sách liên kết	n	n	1	n
Bảng băm	-	n	n	n	Trong trường hợp hàm băm hoàn hảo, chi phí sẽ là O(1)
Cây tìm kiếm nhị phân	n	n	n	n	Trong trường hợp cây cân bằng, chi phí sẽ là O(log(n))
Cây B	log(n)	log(n)	log(n)	log(n)
Cây đỏ đen	log(n)	log(n)	log(n)	log(n)
Cây AVL	log(n)	log(n)	log(n)	log(n)
Bộ lọc Bloom	-	1	1	-	Có thể có kết quả dương tính giả trong khi tìm kiếm

Độ phức tạp của các thuật toán sắp xếp mảng

Tên	Tốt nhất	Trung bình	Tệ nhất	Bộ nhớ	Ổn định	Bình luận
Sắp xếp nổi bọt	n	n²	n²	1	Có
Sắp xếp chèn	n	n²	n²	1	Có
Sắp xếp chọn	n²	n²	n²	1	Không
Sắp xếp vun đống	n log(n)	n log(n)	n log(n)	1	Không
Sắp xếp trộn	n log(n)	n log(n)	n log(n)	n	Có
Sắp xếp nhanh	n log(n)	n log(n)	n²	log(n)	Không	Sắp xếp nhanh thường được thực hiện tại chỗ với không gian ngăn xếp O (log (n))
Shell sort	n log(n)	phụ thuộc vào khoảng cách dãy	n (log(n))²	1	Không
Sắp xếp đếm	n + r	n + r	n + r	n + r	Có	r - số lớn nhất trong mảng
Sắp xếp theo cơ số	n * k	n * k	n * k	n + k	Có	k - độ dài của khóa dài nhất

Project Backers

Bạn có thể hỗ trợ dự án này qua ❤️️ GitHub hoặc ❤️️ Patreon.

Những người đang ủng hộ dự án này ∑ = 0