✂️ Chia để trị

Chia để trị (divide and conquer) là một chiến lược giải bài toán rất tự nhiên: nếu bài toán gốc quá lớn để giải trực tiếp, hãy chia nó thành các bài toán con nhỏ hơn nhưng cùng dạng, giải từng bài toán con (thường bằng cách đệ quy - áp dụng lại chính chiến lược này), rồi ghép kết quả các bài toán con lại để có lời giải cho bài toán gốc.

Ba câu hỏi giúp nhận ra một bài toán có hợp với chia để trị hay không:

Có thể chia nhỏ không? Bài toán gốc có thể tách thành các bài toán con cùng dạng, nhỏ hơn.
Các bài toán con có độc lập không? Giải bài toán con này không phụ thuộc kết quả bài toán con khác - nhờ vậy có thể giải riêng lẻ (thậm chí song song).
Có ghép được không? Từ lời giải của các bài toán con, có cách kết hợp lại thành lời giải bài toán gốc.

Ví dụ quen thuộc: Merge Sort

Trang Sắp xếp đã giới thiệu Merge Sort, và đây chính là ví dụ kinh điển nhất của chia để trị: chia mảng làm đôi, đệ quy sắp xếp từng nửa (bài toán con cùng dạng với bài toán gốc - “sắp xếp một mảng”, chỉ nhỏ hơn), rồi trộn (merge) hai nửa đã sắp xếp lại thành một mảng hoàn chỉnh - đây chính là bước “ghép kết quả”.

Điều thú vị là chia để trị không chỉ giúp code gọn hơn mà còn thường cải thiện độ phức tạp: các thuật toán sắp xếp O(n²) như bubble sort xử lý toàn bộ mảng trong một khối, còn Merge Sort nhờ chia nhỏ liên tục mà đạt O(n log n) - nhanh hơn hẳn khi dữ liệu lớn.

Lũy thừa nhanh

Tính xⁿ theo cách thông thường (nhân x liên tiếp n lần) tốn O(n). Áp dụng chia để trị, ta nhận ra một tính chất: xⁿ = (x^(n/2))² khi n chẵn. Điều này nghĩa là để tính xⁿ, chỉ cần tính x^(n/2) (một bài toán con bằng một nửa kích thước) rồi bình phương lên.

def fast_pow(x, n):
    if n == 0:
        return 1
    half = fast_pow(x, n // 2)       # bài toán con: kích thước giảm 1 nửa
    if n % 2 == 0:
        return half * half
    else:
        return half * half * x       # n lẻ: nhân bù thêm 1 lần x

fast_pow(2, 10)  # 1024, chỉ tốn ~4 lần nhân thay vì 10

Mỗi lần gọi đệ quy, n giảm đi một nửa - giống hệt binary search - nên độ sâu đệ quy chỉ là log n, đưa độ phức tạp từ O(n) xuống O(log n). Đây là minh chứng rõ ràng cho lợi ích thứ hai của chia để trị: không chỉ tổ chức code gọn hơn, mà bản thân việc chia đôi liên tục có thể thay đổi hẳn bậc độ phức tạp.

Tháp Hà Nội (Tower of Hanoi)

Bài toán kinh điển: có 3 cột A, B, C; cột A ban đầu xếp n đĩa to dần từ trên xuống. Cần chuyển toàn bộ n đĩa sang cột C, mỗi lần chỉ được di chuyển 1 đĩa trên cùng của một cột, và không bao giờ được đặt đĩa to lên đĩa nhỏ hơn.

Nhìn qua, bài toán không rõ chia nhỏ ở đâu. Chìa khóa là coi (n-1) đĩa trên cùng là một khối duy nhất: để chuyển n đĩa từ A sang C (dùng B làm trung gian), ta chỉ cần ba bước, mỗi bước là một bài toán con nhỏ hơn:

Chuyển n-1 đĩa trên cùng từ A sang B (dùng C làm trung gian) - bài toán con cùng dạng, kích thước n-1.
Chuyển đĩa to nhất còn lại từ A sang C trực tiếp - 1 bước đơn giản.
Chuyển n-1 đĩa từ B sang C (dùng A làm trung gian) - lại một bài toán con kích thước n-1.

def hanoi(n, src, buf, tar, moves):
    if n == 1:
        moves.append((src, tar))    # base case: 1 đĩa, chuyển thẳng
        return
    hanoi(n - 1, src, tar, buf, moves)  # bước 1: n-1 đĩa, A -> B (qua C)
    moves.append((src, tar))             # bước 2: đĩa lớn nhất, A -> C
    hanoi(n - 1, buf, src, tar, moves)  # bước 3: n-1 đĩa, B -> C (qua A)

moves = []
hanoi(3, "A", "B", "C", moves)

Mỗi lời gọi tách thành 2 lời gọi con kích thước n-1, tạo thành cây đệ quy có n tầng và 2ⁿ - 1 lời gọi - độ phức tạp thời gian O(2ⁿ). Con số này giải thích vì sao truyền thuyết “64 đĩa vàng” đi kèm bài toán này lại gắn với một khoảng thời gian dài không tưởng: 2⁶⁴ bước, dù mỗi giây chuyển một đĩa, vẫn mất hàng tỷ năm.

Tóm tắt

Chia để trị: chia bài toán thành các bài toán con cùng dạng, giải đệ quy, rồi ghép kết quả lại.
Ba điều kiện để áp dụng: chia nhỏ được, các phần độc lập, và ghép lại được.
Đôi khi chia để trị chỉ để code gọn hơn (Tháp Hà Nội); đôi khi nó thực sự đổi bậc độ phức tạp (Merge Sort: O(n²) → O(n log n); lũy thừa nhanh: O(n) → O(log n)).