Chuyển tới nội dung chính

Chia để trị (giới thiệu)

Bạn sẽ học được gì

Chia để trị (divide and conquer) là một mẫu đệ quy cực mạnh: chia bài toán lớn thành các bài nhỏ hơn, giải từng cái, rồi ghép kết quả lại. Đây là nền của merge sort, quick sort, binary search và rất nhiều thuật toán nhanh.

1. Trực quan: đếm phiếu bầu cả nước​

Phải đếm phiếu của cả nước — quá nhiều để một người làm. Cách thông minh:

              Cả nước
            /         \
        Miền Bắc     Miền Nam        ← CHIA: tách đôi
        /     \       /     \
     Tỉnh A  Tỉnh B  ...    ...      ← chia tiếp tới khi nhỏ đủ để đếm tay
        |       |
       12      8                     ← TRỊ: đếm từng phần nhỏ
        \      /
         20 (Bắc) ... + ... (Nam)    ← GHÉP: cộng kết quả lên
            \         /
             Tổng cả nước

Ba bước của chia để trị: Chia (tách bài toán) → Trị (giải các phần, thường bằng đệ quy) → Ghép (kết hợp kết quả con thành kết quả lớn).

2. Khung tổng quát​

def chia_de_tri(bai_toan):
    if bai_toan đủ nhỏ:              # BASE CASE
        return giải_trực_tiếp(bai_toan)
    phần_1, phần_2 = chia(bai_toan)  # CHIA
    kq1 = chia_de_tri(phần_1)        # TRỊ (đệ quy)
    kq2 = chia_de_tri(phần_2)        # TRỊ (đệ quy)
    return ghép(kq1, kq2)            # GHÉP

Để ý: nó chính là đệ quy với base case "đủ nhỏ" — nhưng mỗi tầng chia thành nhiều phần rồi ghép lại, khác với đệ quy tuyến tính ở các bài trước.

3. Ví dụ: tính tổng mảng bằng chia để trị​

Đang tải trình chạy code…

Mảng bị chia đôi liên tục thành các cây nhỏ, đếm ở lá, rồi cộng ngược lên — đúng mô hình đếm phiếu ở trên.

4. Vì sao chia để trị thường NHANH?​

Chia đôi liên tục tạo ra cây sâu khoảng log n tầng (xem bài 1.2.2 mục 7). Nếu mỗi tầng xử lý tổng cộng n việc, tổng là n × log n — nhanh hơn nhiều so với n² của cách ngây thơ. Đây là lý do:

  • Merge sort: chia đôi, sắp xếp 2 nửa, trộn lại → O(n log n).
  • Binary search: chia đôi, chỉ trị một nửa (vứt nửa kia) → O(log n).

Mẹo: chia đôi + làm việc tuyến tính mỗi tầng → thường ra n log n. Chia đôi + chỉ đi một nửa → thường ra log n.

5. Ba bước cần xác định cho mỗi bài​

  1. Base case: nhỏ tới đâu thì giải thẳng?
  2. Chia: tách thành các phần nào? (thường là hai nửa)
  3. Ghép: kết hợp kết quả con ra sao? (cộng, trộn, chọn max...)

Khâu Ghép thường là chỗ quyết định độ khó và tốc độ.

6. Mẫu nhận diện​

  • Bài toán chia đôi được và lời giải các nửa ghép lại được thành lời giải cả bài.
  • Dữ liệu đã sắp xếp + muốn nhanh → nghĩ binary search (chia đôi, bỏ một nửa).
  • Cần sắp xếp / trộn / đếm trên mảng lớn → nghĩ merge sort (chia đôi, trộn).

7. 🎮 Trò chơi: Nhận diện chia để trị​

🎮 Chia để trị?Câu 1/4· Điểm 0· 🔥 0

Chia để trị = chia thành phần nhỏ + giải từng phần + GHÉP kết quả lại.

Trong chia để trị, bước "Ghép" làm gì?

8. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Ba bước của chia để trị là?
2. Vì sao chia để trị thường nhanh?
3. Chia để trị về bản chất là?

9. Hoàn thành​

…

☑️ Tiếp theo: 1.3.5 — Quan hệ truy hồi & Định lý thợ (công thức tính nhanh Big-O của đệ quy).