Khi đọc tài liệu giải thuật hoặc luyện tập trên các trang như LeetCode, bạn sẽ gặp rất nhiều thuật ngữ tiếng Anh. Dưới đây là bảng tổng hợp những thuật ngữ phổ biến nhất, được nhóm theo chủ đề để bạn dễ tra cứu.
| Thuật ngữ (English) |
Tiếng Việt |
Giải thích ngắn gọn |
| Array |
Mảng |
Tập hợp phần tử lưu liên tiếp trong bộ nhớ, truy cập theo chỉ số. |
| Linked List |
Danh sách liên kết |
Chuỗi các node liên kết với nhau qua con trỏ. |
| Stack |
Ngăn xếp |
Cấu trúc LIFO - vào sau ra trước. |
| Queue |
Hàng đợi |
Cấu trúc FIFO - vào trước ra trước. |
| Deque |
Hàng đợi hai đầu |
Cho phép thêm/xóa ở cả hai đầu. |
| Hash Table |
Bảng băm |
Lưu trữ theo cặp key-value, tra cứu gần như O(1). |
| Hash Collision |
Va chạm băm |
Hai key khác nhau bị ánh xạ vào cùng một vị trí trong bảng băm. |
| Binary Tree |
Cây nhị phân |
Mỗi node có tối đa hai node con. |
| Binary Search Tree (BST) |
Cây tìm kiếm nhị phân |
Cây nhị phân có thứ tự: trái nhỏ hơn gốc, phải lớn hơn gốc. |
| AVL Tree |
Cây AVL |
Cây tìm kiếm nhị phân tự cân bằng chiều cao. |
| Balanced Tree |
Cây cân bằng |
Cây có chiều cao hai nhánh con luôn chênh lệch trong giới hạn cho phép. |
| Heap |
Đống (Heap) |
Cây nhị phân gần hoàn chỉnh, thỏa tính chất min-heap hoặc max-heap. |
| Priority Queue |
Hàng đợi ưu tiên |
Cấu trúc lấy ra phần tử có độ ưu tiên cao nhất trước, thường cài bằng heap. |
| Graph |
Đồ thị |
Tập hợp đỉnh (vertex) và cạnh (edge) nối giữa chúng. |
| Adjacency List |
Danh sách kề |
Biểu diễn đồ thị bằng danh sách các đỉnh kề của từng đỉnh. |
| Adjacency Matrix |
Ma trận kề |
Biểu diễn đồ thị bằng ma trận đánh dấu cạnh giữa các đỉnh. |
| Thuật ngữ (English) |
Tiếng Việt |
Giải thích ngắn gọn |
| BFS (Breadth-First Search) |
Duyệt theo chiều rộng |
Duyệt đồ thị/cây theo từng lớp, dùng hàng đợi. |
| DFS (Depth-First Search) |
Duyệt theo chiều sâu |
Duyệt đồ thị/cây đi sâu hết một nhánh rồi quay lại, dùng đệ quy hoặc ngăn xếp. |
| Binary Search |
Tìm kiếm nhị phân |
Tìm kiếm trong dãy đã sắp xếp bằng cách chia đôi phạm vi tìm mỗi lần. |
| Linear Search |
Tìm kiếm tuyến tính |
Duyệt tuần tự từng phần tử để tìm mục tiêu. |
| Traversal |
Duyệt |
Quá trình đi qua toàn bộ phần tử của một cấu trúc dữ liệu. |
| Preorder / Inorder / Postorder |
Duyệt trước / giữa / sau |
Ba cách duyệt cây nhị phân dựa trên thứ tự thăm gốc so với hai cây con. |
| Topological Sort |
Sắp xếp tô pô |
Sắp xếp các đỉnh của đồ thị có hướng sao cho cạnh nào cũng đi từ đỉnh trước đến đỉnh sau. |
| Recursion |
Đệ quy |
Hàm gọi lại chính nó để giải bài toán con nhỏ hơn. |
| Base Case |
Điều kiện dừng |
Trường hợp đơn giản nhất khiến đệ quy dừng lại, không gọi tiếp. |
| Memoization |
Ghi nhớ (Top-down) |
Lưu lại kết quả bài toán con đã tính để tránh tính lại, thường đi cùng đệ quy. |
| Tabulation |
Lập bảng (Bottom-up) |
Giải bài toán con nhỏ trước, lưu vào bảng rồi suy ra bài toán lớn hơn. |
| Dynamic Programming |
Quy hoạch động |
Kỹ thuật giải bài toán bằng cách chia nhỏ và tái sử dụng kết quả bài toán con. |
| Optimal Substructure |
Cấu trúc con tối ưu |
Lời giải tối ưu của bài toán lớn được xây từ lời giải tối ưu của bài toán con. |
| Overlapping Subproblems |
Bài toán con trùng lặp |
Các bài toán con được tính đi tính lại nhiều lần nếu không lưu kết quả. |
| Greedy Algorithm |
Thuật toán tham lam |
Luôn chọn lựa chọn tốt nhất tại mỗi bước, không xét lại về sau. |
| Divide and Conquer |
Chia để trị |
Chia bài toán thành các phần nhỏ hơn, giải riêng rồi ghép kết quả lại. |
| Backtracking |
Quay lui |
Thử một lựa chọn, nếu không dẫn đến lời giải thì quay lại và thử lựa chọn khác. |
| Pruning |
Cắt tỉa |
Bỏ qua sớm những nhánh chắc chắn không dẫn đến lời giải hợp lệ. |
| Two Pointers |
Hai con trỏ |
Dùng hai chỉ số di chuyển trên dãy để giảm độ phức tạp so với duyệt lồng nhau. |
| Sliding Window |
Cửa sổ trượt |
Duy trì một đoạn con liên tiếp và trượt dần qua dãy để tính toán hiệu quả. |
| Thuật ngữ (English) |
Tiếng Việt |
Giải thích ngắn gọn |
| Time Complexity |
Độ phức tạp thời gian |
Ước lượng thời gian chạy tăng theo kích thước đầu vào. |
| Space Complexity |
Độ phức tạp không gian |
Ước lượng bộ nhớ sử dụng tăng theo kích thước đầu vào. |
| Big O Notation |
Ký hiệu Big O |
Cách biểu diễn cận trên của độ phức tạp khi đầu vào tiến tới vô cực. |
| Amortized |
Khấu hao (trung bình) |
Độ phức tạp trung bình trên nhiều thao tác, dù một vài thao tác riêng lẻ có thể chậm hơn. |
| In-place |
Tại chỗ |
Thuật toán chỉ dùng thêm rất ít bộ nhớ phụ, không cần cấu trúc dữ liệu mới. |
| Stable Sort |
Sắp xếp ổn định |
Giữ nguyên thứ tự tương đối giữa các phần tử có giá trị bằng nhau. |
| Thuật ngữ (English) |
Tiếng Việt |
Giải thích ngắn gọn |
| Load Factor |
Hệ số tải |
Tỷ lệ giữa số phần tử đang lưu và tổng số ô của bảng băm. |
| Collision Resolution |
Xử lý va chạm |
Các chiến lược xử lý khi hai key bị băm vào cùng một vị trí. |
| Chaining |
Nối chuỗi |
Xử lý va chạm bằng cách lưu nhiều phần tử tại cùng một ô dưới dạng danh sách liên kết. |
| Open Addressing |
Địa chỉ mở |
Xử lý va chạm bằng cách tìm một ô trống khác trong chính bảng băm. |
Xem thêm: Giới thiệu
