/javascript-algorithms-and-data-structure

Cấu trúc dữ liệu và giải thuật cho JavaScript

Primary LanguageJavaScript

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

CI codecov

Đâ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)

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

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.

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.

Big O graphs

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