Bảng thuật ngữ¶
Bảng dưới đây liệt kê các thuật ngữ quan trọng xuất hiện trong cuốn sách này. Bạn nên ghi nhớ tên tiếng Anh của từng thuật ngữ để thuận tiện cho việc đọc các tài liệu tiếng Anh.
Bảng
| English | Tiếng Việt |
|---|---|
| algorithm | thuật toán |
| data structure | cấu trúc dữ liệu |
| code | mã nguồn |
| file | tệp |
| function | hàm |
| method | phương thức |
| variable | biến |
| asymptotic complexity analysis | phân tích độ phức tạp tiệm cận |
| time complexity | độ phức tạp thời gian |
| space complexity | độ phức tạp không gian |
| loop | vòng lặp |
| iteration | phép lặp |
| recursion | đệ quy |
| tail recursion | đệ quy đuôi |
| recursion tree | cây đệ quy |
| big-\(O\) notation | ký hiệu \(O\) lớn |
| asymptotic upper bound | giới hạn trên tiệm cận |
| sign-magnitude | dấu lượng trị |
| 1’s complement | bù 1 |
| 2’s complement | bù 2 |
| array | mảng |
| index | chỉ số |
| linked list | danh sách liên kết |
| linked list node, list node | nút danh sách liên kết, nút danh sách |
| head node | nút đầu |
| tail node | nút cuối |
| list | danh sách |
| dynamic array | mảng động |
| hard disk | ổ cứng |
| random-access memory (RAM) | bộ nhớ truy cập ngẫu nhiên (RAM) |
| cache memory | bộ nhớ đệm |
| cache miss | trượt bộ nhớ đệm |
| cache hit rate | tỷ lệ trúng bộ nhớ đệm |
| stack | ngăn xếp |
| top of the stack | đỉnh ngăn xếp |
| bottom of the stack | đáy ngăn xếp |
| queue | hàng đợi |
| double-ended queue | hàng đợi hai đầu |
| front of the queue | đầu hàng đợi |
| rear of the queue | cuối hàng đợi |
| hash table | bảng băm |
| hash set | tập hợp băm |
| bucket | xô |
| hash function | hàm băm |
| hash collision | đụng độ băm |
| load factor | hệ số tải |
| separate chaining | giải pháp kết nối chuỗi |
| open addressing | địa chỉ hóa mở |
| linear probing | dò tuyến tính |
| lazy deletion | xóa lười |
| binary tree | cây nhị phân |
| tree node | nút cây |
| left-child node | nút con trái |
| right-child node | nút con phải |
| parent node | nút cha |
| left subtree | cây con trái |
| right subtree | cây con phải |
| root node | nút gốc |
| leaf node | nút lá |
| edge | cạnh |
| level | mức |
| degree | bậc |
| height | chiều cao |
| depth | độ sâu |
| perfect binary tree | cây nhị phân hoàn hảo |
| complete binary tree | cây nhị phân hoàn chỉnh |
| full binary tree | cây nhị phân đầy đủ |
| balanced binary tree | cây nhị phân cân bằng |
| binary search tree | cây tìm kiếm nhị phân |
| AVL tree | cây AVL |
| red-black tree | cây đỏ-đen |
| level-order traversal | duyệt theo mức |
| breadth-first traversal | duyệt theo chiều rộng |
| depth-first traversal | duyệt theo chiều sâu |
| binary search tree | cây tìm kiếm nhị phân |
| balanced binary search tree | cây tìm kiếm nhị phân cân bằng |
| balance factor | hệ số cân bằng |
| heap | đống |
| max heap | đống cực đại |
| min heap | đống cực tiểu |
| priority queue | hàng đợi ưu tiên |
| heapify | vun đống |
| top-\(k\) problem | bài toán tìm top-\(k\) |
| graph | đồ thị |
| vertex | đỉnh |
| undirected graph | đồ thị vô hướng |
| directed graph | đồ thị có hướng |
| connected graph | đồ thị liên thông |
| disconnected graph | đồ thị không liên thông |
| weighted graph | đồ thị có trọng số |
| adjacency | sự kề nhau |
| path | đường đi |
| in-degree | bán bậc vào |
| out-degree | bán bậc ra |
| adjacency matrix | ma trận kề |
| adjacency list | danh sách kề |
| breadth-first search | tìm kiếm theo chiều rộng (BFS) |
| depth-first search | tìm kiếm theo chiều sâu (DFS) |
| binary search | tìm kiếm nhị phân |
| searching algorithm | thuật toán tìm kiếm |
| sorting algorithm | thuật toán sắp xếp |
| selection sort | sắp xếp chọn |
| bubble sort | sắp xếp nổi bọt |
| insertion sort | sắp xếp chèn |
| quick sort | sắp xếp nhanh |
| merge sort | sắp xếp trộn |
| heap sort | sắp xếp vun đống |
| bucket sort | sắp xếp theo xô |
| counting sort | sắp xếp đếm |
| radix sort | sắp xếp theo cơ số |
| divide and conquer | chia để trị |
| hanota problem | bài toán tháp Hà Nội |
| backtracking algorithm | thuật toán quay lui |
| constraint | ràng buộc |
| solution | lời giải |
| state | trạng thái |
| pruning | cắt tỉa |
| permutations problem | bài toán hoán vị |
| subset-sum problem | bài toán tổng tập hợp con |
| \(n\)-queens problem | bài toán \(n\) quân hậu |
| dynamic programming | quy hoạch động |
| initial state | trạng thái ban đầu |
| state-transition equation | phương trình chuyển trạng thái |
| knapsack problem | bài toán cái túi |
| edit distance problem | bài toán khoảng cách chỉnh sửa |
| greedy algorithm | thuật toán tham lam |