Bảng thuật ngữ
51 thuật ngữ chuẩn dùng xuyên suốt phần luyện thuật toán.
| Tiếng Việt | English | Giải thích |
|---|---|---|
| amortized | amortized | Chi phí trung bình mỗi thao tác qua chuỗi dài thao tác. |
| Bất biến | Invariant | Điều kiện luôn đúng ở mỗi bước của vòng lặp hay thuật toán — chìa khoá để chứng minh tính đúng đắn. |
| Big-O | Big-O | Ký hiệu mô tả độ phức tạp khi n → ∞, bỏ hằng số. |
| brute force | brute force | Cách giải thô — duyệt mọi khả năng, thường O(n²) hoặc tệ hơn. |
| cấu trúc dữ liệu | data structure | Cách tổ chức dữ liệu để thao tác hiệu quả. |
| cây | tree | Đồ thị có hướng không chu trình với 1 gốc. |
| Cây tìm kiếm nhị phân | Binary Search Tree | Cây nhị phân mà mọi node bên trái nhỏ hơn, bên phải lớn hơn — tìm/chèn/xoá O(log n) khi cân bằng. |
| Chia để trị | Divide and Conquer | Chia bài toán thành các phần độc lập, giải từng phần rồi gộp lại — ví dụ merge sort, quick sort. |
| Chuỗi đối xứng | Palindrome | Chuỗi đọc xuôi và đọc ngược đều giống nhau, ví dụ "level". |
| con trỏ | pointer | Biến chỉ tới vị trí trong mảng/chuỗi. |
| Con trỏ nhanh chậm | Fast & Slow Pointers | Hai con trỏ chạy khác tốc độ trên danh sách liên kết — phát hiện chu trình và tìm điểm giữa (thuật toán Floyd). |
| Cửa sổ trượt | Sliding Window | Kỹ thuật duy trì một khung con tiếp di chuyển trên mảng/chuỗi, mỗi bước cập nhật trạng thái O(1). |
| Danh sách kề | Adjacency List | Cách lưu đồ thị: mỗi đỉnh giữ danh sách các đỉnh nối tới nó — tiết kiệm bộ nhớ cho đồ thị thưa. |
| danh sách liên kết | linked list | Chuỗi node trỏ tới nhau, thêm/xoá đầu O(1) nhưng truy cập chỉ số O(n). |
| Dãy con | Subsequence | Dãy giữ nguyên thứ tự nhưng có thể bỏ bớt phần tử — không cần liên tiếp. |
| Đảo chữ | Anagram | Hai chuỗi gồm cùng tập ký tự với số lượng bằng nhau, chỉ khác thứ tự sắp xếp. |
| đệ quy | recursion | Hàm gọi chính nó với input nhỏ hơn. |
| độ phức tạp bộ nhớ | space complexity | Bộ nhớ phụ trợ thuật toán cần. |
| độ phức tạp thời gian | time complexity | Số bước thực thi theo kích thước input. |
| đồ thị | graph | Tập đỉnh nối nhau bởi cạnh. |
| Ghi nhớ | Memoization | Cache kết quả mỗi lời gọi đệ quy theo tham số để mỗi trạng thái chỉ tính một lần (top-down). |
| Hai con trỏ | Two-Pointer | Dùng 2 con trỏ chạy ngược/đồng hướng để khám phá mảng đã sắp xếp hoặc tìm cặp thoả điều kiện. |
| hàng đợi | queue | Cấu trúc FIFO — vào trước ra trước. |
| Hàng đợi ưu tiên | Priority Queue | Hàng đợi luôn lấy ra phần tử ưu tiên cao nhất (nhỏ nhất hoặc lớn nhất), thường cài bằng heap, chèn/lấy O(log n). |
| hash collision | hash collision | 2 key khác nhau hash ra cùng index. |
| Hash Map | Hash Map | Cấu trúc dữ liệu lưu cặp key→value với tra cứu trung bình O(1). |
| Heap | Heap | Cây nhị phân với tính chất min/max ở gốc, thao tác O(log n). |
| Khoảng | Intervals | Bài xử lý danh sách cặp [start, end] — sắp xếp theo start rồi gộp/chèn các khoảng chồng nhau. |
| mảng | array | Danh sách phần tử đặt liền kề trong bộ nhớ, truy cập theo chỉ số O(1). |
| Mảng con | Subarray | Đoạn các phần tử liên tiếp nằm trong mảng. |
| monotonic stack | monotonic stack | Stack với phần tử luôn tăng/giảm dần, dùng cho next-greater-element. |
| ngăn xếp | stack | Cấu trúc LIFO — vào sau ra trước. |
| Quay lui | Backtracking | Thử mọi khả năng, đụng ràng buộc thì quay lại bước trước thử khả năng khác. |
| Quy hoạch động | Dynamic Programming | Chia bài toán thành các bài con gối nhau, lưu kết quả để khỏi tính lại — thường dựng bằng đệ quy + ghi nhớ hoặc bảng dp. |
| Quy hoạch động 1 chiều | DP-1D | Lưu kết quả bài toán con vào mảng 1 chiều dp[] để tránh tính lại. |
| Sắp xếp tô-pô | Topological Sort | Xếp thứ tự các đỉnh của đồ thị có hướng không chu trình sao cho mọi cạnh u→v đều có u đứng trước v. |
| Tại chỗ | In-place | Biến đổi dữ liệu ngay trên cấu trúc gốc, dùng bộ nhớ phụ O(1), không tạo bản sao. |
| Tập băm | Hash Set | Tập hợp các phần tử không trùng, kiểm tra tồn tại trung bình O(1). |
| tham lam | greedy | Mỗi bước chọn lựa tốt nhất tại thời điểm đó, không tính xa. |
| thuật toán | algorithm | Chuỗi bước rõ ràng để giải một bài toán. |
| Thuật toán Kadane | Kadane's Algorithm | Tìm mảng con liên tiếp có tổng lớn nhất trong O(n) bằng cách cộng dồn và reset khi tổng âm. |
| Tìm kiếm nhị phân | Binary Search | Cắt nửa không gian tìm kiếm mỗi bước trên mảng đã sắp xếp, đạt O(log n). |
| Tìm kiếm theo chiều rộng | BFS | Duyệt đồ thị/cây theo từng tầng, dùng queue, hữu ích cho đường ngắn nhất không trọng số. |
| Tìm kiếm theo chiều sâu | DFS | Duyệt đồ thị/cây bằng cách đi sâu hết một nhánh rồi quay lại, dùng stack hoặc đệ quy. |
| tối ưu | optimal | Giải pháp tốt nhất theo tiêu chí cho trước (thường là time hoặc space). |
| Tổng tiền tố | Prefix Sum | Mảng cộng dồn để lấy tổng đoạn [i, j] trong O(1) sau khi tiền xử lý O(n). |
| trade-off | trade-off | Đánh đổi giữa 2 tiêu chí (thường time vs space). |
| Trie | Trie | Cây tiền tố, mỗi node là 1 ký tự, dùng cho autocomplete và prefix search. |
| trường hợp biên | edge case | Input bất thường ở ranh giới (rỗng, 1 phần tử, max). |
| Union-Find | Union-Find | Cấu trúc quản lý các tập rời nhau, hỗ trợ gộp tập (union) và tìm đại diện (find) gần như O(1) nhờ path compression và union by rank. Còn gọi là DSU. |
| vòng lặp | iteration | Lặp lại các bước qua for/while. |
Hiện 51 / 51 thuật ngữ