📚 Thuật ngữ DSA thường gặp

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.

Cấu trúc dữ liệ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.

Giải thuật

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ả.

Độ phức tạp

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.

Kỹ thuật xử lý xung đột băm

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ý xung đột	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ý xung đột 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ý xung đột 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