Bạn sẽ học được gì
- Phân tích độ phức tạp thời gian và bộ nhớ bằng ký hiệu Big-O
- Cài đặt và chọn đúng cấu trúc dữ liệu: mảng động, danh sách, ngăn xếp, hàng đợi, bảng băm, cây, heap
- Nắm các thuật toán sắp xếp và tìm kiếm cùng ưu nhược điểm của từng loại
- Giải bài toán đồ thị: BFS, DFS, đường đi ngắn nhất
- Thiết kế lời giải bằng chia để trị, tham lam và quy hoạch động
Nên học trước
Giới thiệu
Cấu trúc dữ liệu và giải thuật (CTDL>) là môn học về cách tổ chức dữ liệu và cách giải bài toán hiệu quả. Hai chương trình cùng cho kết quả đúng có thể chênh nhau hàng nghìn lần về tốc độ chỉ vì chọn sai cấu trúc dữ liệu — và môn học này dạy bạn nhìn ra điều đó trước khi viết code.
Học để làm gì
- Viết chương trình chạy nhanh và mở rộng được khi dữ liệu tăng từ nghìn lên triệu bản ghi.
- Là nội dung chính của phỏng vấn kỹ thuật ở hầu hết công ty phần mềm và của các kỳ thi lập trình.
- Là nền tảng cho cơ sở dữ liệu, hệ điều hành, trình biên dịch và trí tuệ nhân tạo.
Một vòng học hiệu quả cho mỗi chủ đề
- Hiểu ý tưởng qua bài giảng hoặc hình minh họa (vẽ trạng thái cấu trúc dữ liệu sau mỗi thao tác).
- Tự cài đặt từ đầu, không dùng thư viện có sẵn.
- Phân tích độ phức tạp của từng thao tác và so sánh với cách làm khác.
- Luyện bài tập áp dụng — bắt đầu từ bài dễ, tăng dần.
Nên dùng ngôn ngữ nào?
Python giúp tập trung vào ý tưởng; C++ hoặc Java giúp hiểu rõ bộ nhớ và phổ biến trong thi lập trình. Chọn một ngôn ngữ bạn đã quen và giữ nguyên suốt lộ trình.
Lưu ý: đừng học thuộc lời giải. Với mỗi bài, hãy viết ra vì sao chọn cấu trúc dữ liệu đó — đây mới là kỹ năng dùng được lâu dài.
Giáo trình & sách tham khảo
Xem tất cả trong tab SáchGiáo trình chính
Introduction to Algorithms
Thomas H. Cormen, Charles E. Leiserson và 2 tác giả khác · 2022 · Bản thứ 4
Vì sao chọn: Giáo trình của MIT 6.006 — cùng bộ bài giảng video trong lộ trình. Đầy đủ và chặt chẽ, là tài liệu tra cứu chuẩn về thuật toán; không cần đọc hết, hãy theo đúng các chương ghi ở từng bước.
Nên đọc: Chương 2–4, 6–8, 10–16, 20–22
Open Data Structures
Pat Morin · 2013
Sách mở (CC BY) giải thích và cài đặt đầy đủ từng cấu trúc dữ liệu, có bản Java, C++ và mã giả — hợp để vừa đọc vừa tự code ở bước 2–5.
Nên đọc: Chương 1–3, 5–6, 9–12
Algorithms
Jeff Erickson · 2019
Sách mở (CC BY 4.0) dạy cách tư duy để thiết kế thuật toán — đệ quy, quy hoạch động, tham lam, đồ thị — với nhiều bài tập hay; bổ sung tốt cho bước 5–6.
Nên đọc: Chương 1, 3–6 và 8
Các bước học
Đăng nhập để đánh dấu các bước đã hoàn thành.
Bước 1: Phân tích độ phức tạp
khoảng 4 giờKý hiệu Big-O, Big-Omega, Big-Theta; đếm số thao tác của vòng lặp lồng nhau và đệ quy. Làm bài tập ước lượng độ phức tạp.
- Đọc: Chương 2 Getting Started, Chương 3 Characterizing Running Times — Introduction to Algorithms
Bước 2: Cấu trúc tuyến tính: mảng, danh sách, ngăn xếp, hàng đợi
khoảng 6 giờMảng động và phân tích khấu hao, danh sách liên kết, ngăn xếp, hàng đợi. Tự cài đặt từng cấu trúc và so sánh chi phí các thao tác.
- Đọc: Chương 10 Elementary Data Structures, Chương 16 Amortized Analysis — Introduction to Algorithms
- Đọc: Chương 2 Array-Based Lists, Chương 3 Linked Lists — Open Data Structures
Bước 3: Sắp xếp và bảng băm
khoảng 8 giờSắp xếp chèn, trộn, nhanh; giới hạn O(n log n) của sắp xếp so sánh và sắp xếp tuyến tính. Bảng băm và cách xử lý va chạm.
- Đọc: Chương 7 Quicksort, Chương 8 Sorting in Linear Time, Chương 11 Hash Tables — Introduction to Algorithms
- Đọc: Chương 5 Hash Tables, Chương 11 Sorting Algorithms — Open Data Structures
Bước 4: Cây, cây cân bằng và heap
khoảng 8 giờCây nhị phân tìm kiếm, cân bằng AVL / đỏ-đen, heap và hàng đợi ưu tiên. Vẽ các phép xoay cây bằng tay trước khi cài đặt.
- Đọc: Chương 6 Heapsort, Chương 12 Binary Search Trees, Chương 13 Red-Black Trees — Introduction to Algorithms
- Đọc: Chương 6 Binary Trees, Chương 9 Red-Black Trees, Chương 10 Heaps — Open Data Structures
Bước 5: Đồ thị: duyệt và đường đi ngắn nhất
khoảng 10 giờBiểu diễn đồ thị, BFS, DFS, sắp xếp tô-pô, Dijkstra và Bellman-Ford. Áp dụng vào bài toán tìm đường trên bản đồ.
- Đọc: Chương 20 Elementary Graph Algorithms, Chương 22 Single-Source Shortest Paths — Introduction to Algorithms
- Đọc: Chương 12 Graphs — Open Data Structures
- Đọc: Chương 5 Basic Graph Algorithms, Chương 6 Depth-First Search, Chương 8 Shortest Paths — Algorithms
Bước 6: Chia để trị, tham lam và quy hoạch động
khoảng 10 giờNhận diện bài toán con chồng lấp, lập công thức truy hồi, cài đặt bằng bảng; so sánh với chiến lược tham lam. Luyện các bài kinh điển: dãy con tăng dài nhất, cái túi, chuỗi con chung dài nhất.
- Đọc: Chương 4 Divide-and-Conquer, Chương 14 Dynamic Programming, Chương 15 Greedy Algorithms — Introduction to Algorithms
- Đọc: Chương 1 Recursion, Chương 3 Dynamic Programming, Chương 4 Greedy Algorithms — Algorithms
Khái niệm chính
- Ký hiệu Big-O
- Mô tả tốc độ tăng của thời gian chạy hay bộ nhớ theo kích thước đầu vào, bỏ qua hằng số: O(1), O(log n), O(n), O(n log n), O(n²)…
- Mảng động
- Mảng tự nhân đôi dung lượng khi đầy; truy cập O(1), thêm vào cuối O(1) khấu hao.
- Bảng băm
- Ánh xạ khóa sang vị trí bằng hàm băm; tìm, thêm, xóa trung bình O(1), cần xử lý va chạm.
- Cây nhị phân tìm kiếm cân bằng
- Cây giữ thứ tự khóa và tự cân bằng (AVL, đỏ-đen) để mọi thao tác chỉ O(log n).
- Heap và hàng đợi ưu tiên
- Cấu trúc luôn lấy ra phần tử nhỏ nhất/lớn nhất trong O(log n); dùng trong Dijkstra và lập lịch.
- Duyệt đồ thị (BFS/DFS)
- Hai cách thăm mọi đỉnh của đồ thị theo chiều rộng hoặc chiều sâu; nền tảng của hầu hết thuật toán đồ thị.
- Quy hoạch động
- Giải bài toán lớn bằng cách lưu lại lời giải các bài toán con chồng lấp, tránh tính lại.
Học xong để làm gì
- Vượt qua vòng phỏng vấn kỹ thuật ở các công ty phần mềm
- Tối ưu truy vấn, bộ nhớ đệm và chỉ mục trong hệ thống backend
- Thi lập trình (Olympic Tin học, ICPC, Codeforces)
- Xây định tuyến, bản đồ, mạng xã hội — các bài toán đồ thị thực tế
- Học tiếp cơ sở dữ liệu, hệ điều hành và trí tuệ nhân tạo
Câu hỏi thường gặp
Cần giỏi toán tới đâu?
Cần logic, quy nạp, một chút tổ hợp và logarit — phần lớn có trong chủ đề Mathematics for Computer Science. Không cần giải tích nâng cao.
Học lý thuyết hay luyện đề trước?
Xen kẽ: học một cấu trúc dữ liệu, tự cài đặt, rồi làm 5–10 bài áp dụng ngay. Luyện đề mà không hiểu nền tảng sẽ nhanh chóng bị chững lại ở bài khó.
Mất bao lâu?
Khoảng 45–50 giờ cho lộ trình cơ bản dưới đây; muốn thành thạo cho phỏng vấn nên cộng thêm 50–100 giờ luyện bài.
Có cần học hết mọi cấu trúc dữ liệu?
Không. Nắm chắc mảng, bảng băm, cây cân bằng, heap và đồ thị đã giải quyết được đa số bài toán thực tế.


