Bỏ qua tới nội dung chính

Hướng dẫn học chủ đề

Cấu trúc dữ liệu và giải thuật

Data Structures and Algorithms

Trung bìnhkhoảng 46 giờ6 bước

Cấu trúc dữ liệu & giải thuật: tổ chức dữ liệu hiệu quả và phân tích độ phức tạp thuật toán.

Bắt đầu học

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&GT) 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ủ đề

  1. 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).
  2. Tự cài đặt từ đầu, không dùng thư viện có sẵn.
  3. 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.
  4. 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ách

Giá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

Có phíTrung bìnhTiếng Anh1.332 trang

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

CC BY 2.5 CanadaCơ bảnTiếng Anh344 trang

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

CC BYTrung bìnhTiếng Anh472 trang

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.

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

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

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

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

  5. 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
  6. 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ế.

Chọn nguồn tự học

Tìm khóa đề cao cài đặt thực hành; các OpenCourseWare của MIT/Stanford/Berkeley là chuẩn tham chiếu phổ biến.