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

Chia để trị sâu hơn

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

Chia để trị (divide and conquer) là tư duy "việc lớn thì bẻ đôi". Ta đã gặp nó ở bài 1.3.4; giờ ta đi sâu hơn với ba bài toán đẹp: đếm nghịch thế, tìm dãy con tổng lớn nhất, và lũy thừa nhanh. Bạn sẽ thấy cùng một mẫu ba bước giải được những bài tưởng chừng rất khác nhau.

1. Trực quan: chia đôi mãi cho tới khi dễ​

Ôn lại tinh thần: gặp bài lớn, chia thành vài bài con nhỏ hơn (thường là hai nửa), giải từng phần (thường bằng đệ quy), rồi gộp các lời giải con thành lời giải lớn.

            [ bai lon ]
            ╱          ╲          CHIA
      [nua trai]    [nua phai]
        ╱  ╲          ╱  ╲        ... chia tiep
      ...  ...      ...  ...
        ╲  ╱          ╲  ╱        GOP nguoc len
      [giai trai]  [giai phai]
            ╲          ╱
            [ ket qua ]           GHEP lai

Ba bước vàng: Chia (divide) → Giải (conquer) → Gộp (combine). Phần "thông minh" của mỗi thuật toán nằm ở bước gộp — đó là nơi quyết định bài có nhanh hay không.

2. Mẫu chung và liên hệ merge sort​

Khung chia để trị:

def giai(bai):
    if bai du nho:            # truong hop co so
        return giai_truc_tiep(bai)
    trai, phai = chia_doi(bai)        # CHIA
    a = giai(trai)                     # GIAI (de quy)
    b = giai(phai)                     # GIAI
    return gop(a, b)                   # GOP

Bạn đã thấy mẫu này ở merge sort (/thuat-toan/merge-sort): chia mảng làm đôi, sắp xếp mỗi nửa, rồi trộn (merge) hai nửa đã sắp. Bước gộp O(n), đệ quy log n tầng → tổng O(n log n). Ba ví dụ dưới đây dùng đúng tinh thần đó.

3. Ví dụ 1: Đếm nghịch thế (inversions)​

Nghịch thế là cặp (i, j) với i < j nhưng a[i] > a[j] — một cặp "đứng sai thứ tự". Số nghịch thế đo độ "lộn xộn" của mảng. Cách ngây thơ duyệt mọi cặp tốn O(n^2); chia để trị làm trong O(n log n) bằng cách đếm khi trộn (như merge sort).

🐞 Đếm nghịch thế khi trộn hai nửa đã sắpBước 1/5
1def tron_va_dem(trai, phai):
2  ket, dem = [], 0
3  i = j = 0
4  while i < len(trai) and j < len(phai):
5      if trai[i] <= phai[j]:
6          ket.append(trai[i]); i += 1
7      else:
8          ket.append(phai[j]); j += 1
9          dem += len(trai) - i   # trai[i:] deu lon hon phai[j]
10  ket += trai[i:] + phai[j:]
11  return ket, dem
Biến tại bước này
trai[2, 4]
phai[1, 3]
i0
j0
dem0
👉 Hai nửa đã sắp. Bắt đầu trộn.
Đang tải trình chạy code…

4. Ví dụ 2: Dãy con liền kề tổng lớn nhất (max subarray)​

Cho mảng có số âm lẫn dương, tìm đoạn liền kề có tổng lớn nhất. Chia để trị: tổng lớn nhất nằm ở nửa trái, nửa phải, hoặc bắc cầu qua giữa. Hai trường hợp đầu giải bằng đệ quy; trường hợp bắc cầu tính bằng cách nới từ giữa ra hai phía.

   [ ...nua trai... | ...nua phai... ]
                    ↑ giua
   bac cau: max (mo rong trai tu giua) + max (mo rong phai tu giua)
Đang tải trình chạy code…

Ghi chú: bài này còn có lời giải O(n) tuyệt đẹp (Kadane), nhưng phiên bản chia để trị O(n log n) ở đây dạy rất rõ tư duy "trái / phải / bắc cầu".

5. Ví dụ 3: Lũy thừa nhanh (fast exponentiation)​

Tính x^n. Cách ngây thơ nhân n lần → O(n). Chia để trị: x^n = (x^(n/2))^2, nên mỗi bước giảm mũ đi một nửa → chỉ O(log n) phép nhân.

   x^8 = (x^4)^2 = ((x^2)^2)^2 = (((x)^2)^2)^2
   moi tang BINH PHUONG ket qua -> chi log n tang
Đang tải trình chạy code…

6. Phân tích: vì sao log n tầng?​

Bài toánCách ngây thơChia để trị
Đếm nghịch thếO(n^2)O(n log n)
Max subarrayO(n^2)O(n log n) (Kadane còn O(n))
Lũy thừa x^nO(n)O(log n)

Lý do chung: mỗi lần chia đôi, chiều cao cây đệ quy là log n. Nếu mỗi tầng làm việc tuyến tính O(n) thì tổng O(n log n); nếu mỗi tầng chỉ làm O(1) thì tổng O(log n). Đây chính là tinh thần của định lý thợ (master theorem) ở bài 1.3.5.

Bẫy thường gặp:

  • Quên trường hợp cơ số → đệ quy không dừng.
  • Bước gộp viết sai/chậm → mất luôn lợi thế của chia để trị.
  • Tạo bản sao mảng vô tội vạ (a[:giua]) tốn bộ nhớ; bản tối ưu truyền chỉ số lo, hi.

7. Mẫu nhận diện: "khi nào nghĩ tới chia để trị"​

  • Bài có thể bẻ đôi tự nhiên và lời giải lớn ghép được từ lời giải hai nửa.
  • Cần hạ O(n^2) xuống O(n log n), hoặc O(n) xuống O(log n).
  • Thấy cụm từ "trộn", "ghép", "bắc cầu qua giữa", "bình phương dần" → tín hiệu chia để trị.
  • Họ hàng gần: merge sort, tìm kiếm nhị phân, đều là chia để trị.

8. 🎮 Trò chơi: Hiểu chia để trị​

🎮 Chia để trị sâu hơnCâu 1/4· Điểm 0· 🔥 0

Chia - giải - gộp. Bước gộp quyết định tốc độ.

Đếm nghịch thế bằng chia để trị nhanh hơn cách ngây thơ vì?

9. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Trong chia để trị, bước nào thường chứa phần "thông minh" quyết định tốc độ?
2. Lũy thừa nhanh đạt độ phức tạp nào?
3. Vì sao nhiều thuật toán chia để trị có log n tầng đệ quy?

10. Hoàn thành​

…

☑️ Tiếp theo: 3.6.1 — Thao tác bit — làm chủ các phép toán trên bit.