Chia để trị (divide and conquer) là một trong những khuôn mẫu mạnh nhất trong giải thuật: merge sort, quicksort, tìm nhị phân — nhiều bài đầu sê-ri này — đều là nó. Ý tưởng đẹp và tổng quát tới mức khi gặp một bài toán khó, phản xạ tự nhiên là "chia đôi rồi ghép lại". Bài này lấy một bài toán mà chia để trị cho một lời giải rất thanh lịch, đo nó, rồi phát hiện một điều khiêm nhường: đẹp và tổng quát không có nghĩa là tối ưu, và đôi khi một vòng lặp tầm thường đánh bại cả một kiến trúc đệ quy tinh xảo.
Khuôn chia để trị, và bước gộp quyết định tất cả
Chia để trị có ba nhịp: chia bài toán thành các bài con nhỏ hơn, trị (giải) từng bài con bằng đệ quy, rồi gộp (combine) các lời giải con thành lời giải chung. Độ phức tạp của cả thuật toán được tóm trong định lý thợ (master theorem): T(n) = a·T(n/b) + chi phí gộp — với a bài con mỗi lần chia, kích thước n/b, cộng công sức để gộp. Điểm mấu chốt ít người để ý: chính bước gộp thường quyết định độ phức tạp cuối cùng. Nếu gộp rẻ, thuật toán nhanh; nếu gộp đắt, mọi công chia nhỏ có thể đổ sông đổ biển.
Bài toán để đo: mảng con tổng lớn nhất — cho một dãy số (có âm có dương), tìm đoạn liên tiếp có tổng lớn nhất. Lời giải chia để trị rất đẹp: đoạn tốt nhất hoặc nằm gọn trong nửa trái, hoặc gọn trong nửa phải, hoặc bắc qua giữa. Hai trường hợp đầu giải bằng đệ quy trên hai nửa; trường hợp bắc qua giữa là bước gộp — quét từ điểm giữa ra hai phía tìm tổng lớn nhất chạm giữa, tốn O(n). Ghép lại theo định lý thợ: T(n) = 2T(n/2) + O(n) cho ra O(n log n). Nghe chặt chẽ, thông minh, và tối ưu cho một bài trông hóc búa. Tôi đo, và mang theo cả một lời giải ngây thơ lẫn một lời giải khác để so.
Đo: cả ba cùng đáp số, nhưng lệch nhau 20 lần
Tôi cài ba cách: brute O(n²) thử mọi đoạn; chia để trị O(n log n); và Kadane O(n) — một vòng quét tuyến tính duy nhất, giữ "tổng tốt nhất kết thúc tại đây" và cập nhật khi đi. Trước hết kiểm cả ba cho cùng đáp số (chúng khớp), rồi bấm giờ.
Brute O(n²) đúng như dự đoán, thời gian gấp bốn mỗi khi n gấp đôi (6 → 24 → 99 → 389 mili giây ở n = 5.000 đến 40.000), và ở n vài trăm nghìn thì vô dụng. Câu chuyện thật nằm ở hai lời giải "nhanh":
n chia để trị (O(n log n)) Kadane (O(n))
1 triệu 9,6 ms 0,5 ms
10 triệu 111,9 ms 5,3 ms (chia để trị chậm hơn ~21 lần)
Chia để trị, lời giải thanh lịch O(n log n) mà sách giáo khoa tự hào, chậm hơn Kadane khoảng 20 lần — và khoảng cách còn nới rộng khi n lớn hơn (đúng cái thừa số log n). Đây là chỗ tôi phải xét lại kỳ vọng của mình.
Một lần tôi đo hớ: đẹp và tổng quát không phải tối ưu
Tôi vào bài với ngầm định rằng chia để trị, vì là kỹ thuật "cao cấp" và cho O(n log n) trên một bài trông khó, hẳn là lời giải tốt. Nó cảm giác tối ưu — có cấu trúc đệ quy đẹp, có bước gộp thông minh, có phân tích định lý thợ gọn gàng. Nhưng đồng hồ chỉ ra một lời giải khiêm tốn hơn nhiều thắng đậm: Kadane chỉ là một vòng for, đi qua mảng đúng một lần, ở mỗi phần tử quyết định "nối vào đoạn đang có hay bắt đầu đoạn mới", giữ lại tổng lớn nhất từng thấy. Không đệ quy, không bước gộp, không chia nhỏ — O(n) thuần, và nhanh hơn 20 lần.
Bài học đo lường: chia để trị là một công cụ mạnh và tổng quát, nhưng "mạnh và tổng quát" không đồng nghĩa với "tối ưu cho bài này". Sự tổng quát của nó có giá — chi phí đệ quy, chi phí bước gộp lặp lại ở mỗi tầng — và với một số bài, tồn tại một lời giải tuyến tính khéo léo mà cấu trúc đệ quy không bao giờ đấu lại. Nhìn qua lăng kính định lý thợ thì rõ: O(n log n) của chia để trị đến từ bước gộp O(n) nhân với log n tầng; Kadane xóa bỏ cả cái log n ấy bằng cách không chia gì cả, chỉ tích lũy thông tin trong một lần đi. Tôi suýt viết cả bài ca ngợi lời giải chia để trị "thông minh" mà bỏ qua rằng cái đơn giản hơn vừa nhanh hơn vừa dễ hiểu hơn. Đẹp trên giấy không phải là tiêu chí; đồng hồ mới là.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: đừng dừng ở lời giải đẹp đầu tiên; hỏi có cách đơn giản hơn không. Chia để trị hấp dẫn vì nó cho cảm giác "đã giải xong bài khó một cách thanh lịch", và cảm giác đó dễ khiến ta ngừng tìm. Nhưng nhiều bài có một lời giải tuyến tính một-lượt-quét ẩn dưới, thường dựa trên một quan sát về cách thông tin tích lũy dọc mảng (như Kadane). Trước khi hài lòng với O(n log n), hãy hỏi: mình có thực sự cần chia nhỏ không, hay có thể tính lũy tiến trong một lần đi?
Hệ quả thứ hai: khi buộc phải dùng chia để trị, hãy nhìn kỹ bước gộp — đó là nơi chi phí sống. Định lý thợ cho thấy toàn bộ độ phức tạp thường do bước gộp định đoạt. Nếu bạn gộp O(n) mỗi tầng, bạn được O(n log n); nếu bạn tìm được cách gộp rẻ hơn (hoặc chia thành ít bài con hơn), bạn được nhanh hơn. Tối ưu một thuật toán chia để trị gần như luôn là tối ưu bước gộp, không phải bước chia.
Hệ quả thứ ba là con số mang theo: chia để trị cho mảng con tổng lớn nhất là O(n log n) thanh lịch, nhưng Kadane — một vòng quét O(n) — nhanh hơn ~20 lần (5,3 so với 112ms ở n=10 triệu) và đơn giản hơn hẳn; chia để trị mạnh và tổng quát (là nền của merge sort, quicksort) nhưng đẹp và tổng quát không có nghĩa là tối ưu, và big-O của nó do bước gộp quyết định. Một kỹ thuật danh giá không phải là câu trả lời đúng cho mọi bài; đôi khi câu trả lời đúng là một vòng lặp mà bạn suýt bỏ qua vì nó trông quá tầm thường.
Thử ba mươi giây
Lần tới khi bạn giải xong một bài bằng chia để trị và thấy hài lòng với O(n log n), dừng một nhịp và hỏi: mình có thật sự cần chia đôi không? Thử hình dung đi qua dữ liệu đúng một lần, mang theo vài giá trị tích lũy (tổng đang chạy, cực trị đã thấy, trạng thái gọn) — liệu có đủ để trả lời không? Rất nhiều bài "trông cần đệ quy" hóa ra có một lời giải một-lượt như thế, và nó thường nhanh hơn nhờ bỏ được thừa số log n và thân thiện cache hơn. Nếu tìm được, hãy đo cả hai; nếu vòng quét đơn giản thắng — như Kadane thắng ở đây — bạn vừa học lại bài học rằng lời giải đẹp nhất trên bảng không phải lúc nào cũng là lời giải tốt nhất trên máy.
