Cấu Trúc Dữ Liệu & Giải Thuật với JavaScript

Đây là repository về các giải thuật và cấu trúc dữ liệu phổ biến được viết bằng JavaScript.

Mỗi giải thuật sẽ có một folder và file README giải thích cùng các liên kết khác.

Cấu Trúc Dữ Liệu

Cấu trúc dữ liệu là một phương thức 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 chức năng hoặc hoạt động có thể được triển khai cho dữ liệu.

B - Beginner (Cơ bản), A - Advanced (Nâng cao)

• B Linked List
• B Doubly Linked List
• B Queue
• B Stack
• B Hash Table
• B Heap
• B Priority Queue
• A Trie
• A Tree
  • A Binary Search Tree
  • A AVL Tree
  • A Red-Black Tree
  • A Segment Tree
  • A Fenwick Tree
• A Graph
• A Disjoint Set
• A Bloom Filter

Giải thuật

Giải thuật hay thuật toán là một tập hợp hữu hạn các hướng dẫn được xác định rõ ràng, có thể thực hiện được bằng máy tính, thường để giải quyết một lớp vấn đề hoặc để thực hiện một phép tính.

B - Beginner (Cơ bản), A - Advanced (Nâng cao)

Algorithms by Topic

• Các phép toán (Math)
  • B Bit Manipulation - set/get/cập nhật/xoá bit, nhân/chia hai bit, tạo bit âm etc.
  • B Binary Floating Point - biểu diễn nhị phân của dấu phẩy động.
  • B Factorial
  • B Fibonacci Number - dạng cổ điển và dạng đóng
  • B Prime Factors - tìm thừa số nguyên tố và đếm chúng bằng định lý Hardy-Ramanujan.
  • B Primality Test (kiểm tra nguyên hàm)
  • B Euclidean Algorithm - tìm ước số chung lớn nhất (GCD)
  • B Least Common Multiple - tìm bội số chung nhỏ nhất (LCM)
  • B Sieve of Eratosthenes - tìm tất cả số nguyên tố trong giới hạn được cho.
  • B Is Power of Two - kiểm tra một số có phải luỹ thừa của 2.
  • B Pascal's Triangle - tam giác Pascal.
  • B Complex Number - số phức và các phép toán cơ bản.
  • B Radian & Degree - chuyển từ radian sang độ và ngược lại.
  • B Fast Powering
  • B Horner's method - lược đồ Horner.
  • B Matrices - ma trận và các phép toán cơ bản (cộng, nhân, chuyển đổi, etc.)
  • B Euclidean Distance - khoảng cách giữa hai điểm/vector/ma trận.
  • A Integer Partition
  • A Square Root - phương thức Newton.
  • A Liu Hui π Algorithm - tính gần đúng π dựa trên N-gons(Pending)
  • A Discrete Fourier Transform - phép biến đổi Fourier.(Pending)
• Tập hợp (Sets)
  • B Cartesian Product - tích Descartes.
  • B Fisher–Yates Shuffle - thuật toán ngẫu nhiên không trùng.
  • A Power Set - tất cả các tập hợp con của một tập hợp (dùng phương pháp quay lùi)
  • A Permutations (sử dụng và không sử dụng vòng lặp)
  • A Combinations (sử dụng và không sử dụng vòng lặp)
  • A Longest Common Subsequence (LCS)
  • A Longest Increasing Subsequence
  • A Shortest Common Supersequence (SCS)
  • A Knapsack Problem (Pending)
  • A Maximum Subarray (Pending)
  • A Combination Sum (Pending)
• Chuỗi (Strings)
  • B Hamming Distance - khoảng cách Hamming
  • A Levenshtein Distance - khoảng cách Levenshtein
  • A Knuth–Morris–Pratt Algorithm (Thuật toán KMP) - tìm kiếm chuỗi con (so sánh mẫu)(Pending)
  • A Z Algorithm - tìm kiếm chuỗi con (so sánh mẫu)(Pending)
  • A Rabin Karp Algorithm - tìm kiếm chuỗi con(Pending)
  • A Longest Common Substring(Pending)
  • A Regular Expression Matching(Pending)
• Thuật toán tìm kiếm (Searches)
  • B Linear Search
  • B Jump Search (or Block Search) - tìm kiếm trong mảng đã sắp xếp.
  • B Binary Search - tìm kiếm trong mảng đã sắp xếp.
  • B Interpolation Search - tìm kiếm trong mảng được sắp xếp được phân phối thống nhất.
• Thuật toán sắp xếp (Sorting)
  • B Bubble Sort
  • B Selection Sort
  • B Insertion Sort
  • B Heap Sort
  • B Merge Sort
  • B Quicksort
  • B Shellsort
  • B Counting Sort
  • B Radix Sort
• Danh sách liên kết (Linked Lists)
  • B Straight Traversal
  • B Reverse Traversal
• Cây (Trees)
  • B Depth-First Search (DFS)
  • B Breadth-First Search (BFS)
• Lưu đồ (Graphs)
  • B Depth-First Search (DFS)
  • B Breadth-First Search (BFS)
  • B Kruskal’s Algorithm - tìm cây con nhỏ nhất của một đồ thị vô hướng có trọng số.
  • A Dijkstra Algorithm - tìm đường đi ngắn nhât của một đồ thị có hướng không trọng số.(Pending)
  • A Bellman-Ford Algorithm - tính các đường đi ngắn nhất trong một đồ thị có hướng có trọng số. (Pending)
  • A Floyd-Warshall Algorithm - tìm đường đi ngắn nhât của một đồ thị có hướng dựa trên đỉnh trung gian. (Pending)
  • A Detect Cycle - cho cả đồ thị có hướng và vô hướng (DFS and Disjoint Set based versions). (Pending)
  • A Prim’s Algorithm - giống thuật toán Kruskal's. (Pending)
  • A Topological Sorting - phương thức DFS. (Pending)
  • A Articulation Points - thuật toán của Tarjan(dựa trên DFS). (Pending)
  • A Bridges
  • A Eulerian Path and Eulerian Circuit - giải thuật Fleury(Pending)
  • A Hamiltonian Cycle - Đi qua mọi đỉnh chính xác một lần.(Pending)
  • A Strongly Connected Components - giải thuật Kosaraju(Pending)
  • A Travelling Salesman Problem - đường đi ngắn nhất qua mọi điểm và trở về vị trí ban đầu.(Pending)
• Mã hoá
  • B Polynomial Hash - hàm băm dựa trên đa thức
  • B Rail Fence Cipher - mã hoá bằng phương pháp chuyển vị.
  • B Caesar Cipher - mã hoá bằng phương pháp thay thế.
  • B Hill Cipher - má hoá bằng phương pháp tuyến tính.
• Máy học(Pending)
  • B NanoNeuron - 7 hàm JS đơn giản minh họa cách máy móc thực sự có thể học (truyền tiến / lùi)
  • B k-NN - thuật toán K láng giềng gần nhất
  • B k-Means - thuật toán phân cụm k-Means
• Xứ lý hình ảnh(Pending)
  • B Seam Carving - thuật toán thay đổi kích thước hình ảnh.
• Khác
  • B Tower of Hanoi - bài toán tháp Hà Nội.
  • B Square Matrix Rotation
  • B Jump Game - ví dụ về giải thuât quay lùi, tham lam và quy hoạch động.
  • B Unique Paths - ví dụ về giải thuật quay lùi, quy hoạch động và tam giác Pascal.
  • B Rain Terraces -
  • B Recursive Staircase - đếm số cách đi hết cầu thang (4 giải pháp)
  • B Best Time To Buy Sell Stocks - ví dụ về chia để trị.
  • A N-Queens Problem - bài toán N quân hậu.
  • A Knight's Tour - bài toán ngựa đi đường.

Mô hình thuật toán

Mô 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à sự trừu tượng cao hơn một chương trình máy tính.

• Phá mã Brute Force - xem xét tất cả các khả năng và chọn giải pháp tốt nhất
  • B Linear Search
  • B Rain Terraces
  • B Recursive Staircase
  • A Maximum Subarray
  • A Travelling Salesman Problem
  • A Discrete Fourier Transform - biến đổi Fourier.
• Giải thuật tham lam - chọn phương án tốt nhất tại thời điểm hiện tại mà không cần cân nhắc đến các lựa chọn khác trong tương lai.
  • B Jump Game
  • A Unbound Knapsack Problem
  • A Dijkstra Algorithm
  • A Prim’s Algorithm
  • A Kruskal’s Algorithm
• Giải thuật chia để trị - chia nhỏ vấn đề và giải quyết các vấn đề nhỏ đấy.
  • B Binary Search
  • B Tower of Hanoi
  • B Pascal's Triangle
  • B Euclidean Algorithm
  • B Merge Sort
  • B Quicksort
  • B Tree Depth-First Search (DFS)
  • B Graph Depth-First Search (DFS)
  • B Matrices -tạo và duyệt các ma trận có hình dạng khác nhau.
  • B Jump Game
  • B Fast Powering
  • B Best Time To Buy Sell Stocks
  • A Permutations
  • A Combinations
• 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 Fibonacci Number
  • B Jump Game
  • B Unique Paths
  • B Rain Terraces
  • B Recursive Staircase
  • B Seam Carving -
  • A Levenshtein Distance
  • A Longest Common Subsequence (LCS)
  • A Longest Common Substring
  • A Longest Increasing Subsequence
  • A Shortest Common Supersequence
  • A 0/1 Knapsack Problem
  • A Integer Partition
  • A Maximum Subarray
  • A Bellman-Ford Algorithm
  • A Floyd-Warshall Algorithm
  • A Regular Expression Matching
• Giải thuật quay lùi - tương tự brute force ta cũng tìm tất cả các khả năng nhưng trong quá trình tìm kiếm, nếu ta gặp một hướng lựa chọn không thỏa mãn, ta quay lùi về điểm lựa chọn nơi có các hướng khác và thử hướng lựa chọn tiếp theo. Khi đã thử hết các lựa chọn xuất phát từ điểm lựa chọn đó, ta quay lại điểm lựa chọn trước đó và thử hướng lựa chọn tiếp theo tại đấy. Quá trình tìm kiếm thất bại khi không còn điểm lựa chọn nào nữa.
  • B Jump Game
  • B Unique Paths
  • B Power Set
  • A Hamiltonian Cycle
  • A N-Queens Problem
  • A Knight's Tour
  • A Combination Sum
• Giải thuật nhánh cận - ghi nhớ chi phí thấp nhất được tìm thấy ở các giải pháp của giải thuật quay lùi, và sự dụng chi phí đấy như là một ràng buộc để loại bỏ các giải pháp có chi phí lớn hơn. Nói các khác giải thuật nhánh cận là tối ưu của giải thuật quay lùi.

Ký hiệu O lớn

Ký hiệu O được sử dụng để phân loại các thuật toán theo cách thời gian thực thi hoặc yêu cầu không gian bổ sung của chúng. Trong biểu đồ dưới đây, bạn có thể thấy thứ tự phát triển của hầu hết các thuật toán phổ biến được chỉ định trong ký hiệu Big O.

Source: Big O Cheat Sheet.

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

Big O Notation	Computations for 10 elements	Computations for 100 elements	Computations for 1000 elements
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ấu trúc dữ liệu

Data Structure	Access	Search	Insertion	Deletion	Comments
Array	1	n	n	n
Stack	n	n	1	1
Queue	n	n	1	1
Linked List	n	n	1	n
Hash Table	-	n	n	n	In case of perfect hash function costs would be O(1)
Binary Search Tree	n	n	n	n	In case of balanced tree costs would be O(log(n))
B-Tree	log(n)	log(n)	log(n)	log(n)
Red-Black Tree	log(n)	log(n)	log(n)	log(n)
AVL Tree	log(n)	log(n)	log(n)	log(n)
Bloom Filter	-	1	1	-	False positives are possible while searching

Độ phức tạp của giải thuật sắp xếp

Name	Best	Average	Worst	Memory	Stable	Comments
Bubble sort	n	n2	n2	1	Yes
Insertion sort	n	n2	n2	1	Yes
Selection sort	n2	n2	n2	1	No
Heap sort	n log(n)	n log(n)	n log(n)	1	No
Merge sort	n log(n)	n log(n)	n log(n)	n	Yes
Quick sort	n log(n)	n log(n)	n2	log(n)	No	Quicksort is usually done in-place with O(log(n)) stack space
Shell sort	n log(n)	depends on gap sequence	n (log(n))2	1	No
Counting sort	n + r	n + r	n + r	n + r	Yes	r - biggest number in array
Radix sort	n * k	n * k	n * k	n + k	Yes	k - length of longest key

Liên kết

▶ Data Structures and Algorithms on YouTube

Repostiry gốc