Một trong những điều quan trọng nhất khi giải quyết 1 bài toán lập trình đó là xác định được mô hình thiết kế thuật toán phù hợp và tối ưu với yêu cầu mà bài toán đó đưa ra. Phương pháp " Chia để trị " chia một bài toán thành hai hoặc nhiều bài toán nhỏ cùng loại hoặc tương tự với bài toán đã cho, đến khi bài toán trở nên đơn giản nhất để có thể giải quyết trực tiếp. Câu trả lời cho bài toán lớn được tạo ra bằng cách kết hợp các kết quả của các bài toán con.

Cách hoạt động

Chia để trị là một phương pháp giải một vấn đề lớn bằng cách:

Bước 1: Chia bài toán đã cho thành các bài toán con bằng cách đệ quy.

Bước 2: Giải quyết các vấn đề con nhỏ hơn đệ quy. Nếu bài toán con đủ nhỏ sẽ giải quyết trực tiếp.

Bước 3: Kết hợp các kết quả từ bài toán con là một phần của quá trình đệ quy để giải quyết vấn đề thực tế.

Một số bài toán

Tối ưu bài toán tính lũy thừa

Thông thường ta có thể tính aⁿ bằng cách nhân n số a với nhau. Như vậy ta đã thực hiện n phép nhân, độ phức tạp thời gian của phương pháp này là O(n). Ta có thể tối ưu cách giải bài toán này bằng phương pháp chia để trị nhờ nhận xét sau:

aⁿ = a^n/2 . a^n/2 hoặc aⁿ = a . a^n/2 . a^n/2 nếu n lẻ. 

Tính a^n/2 là một bài toán nhỏ hơn do có lũy thừa nhỏ hơn. Ta chỉ cần tính a^n/2 và bình phương kết quả để thu được aⁿ. Số phép nhân thực hiện là n/2 + 1 nếu n chẵn hoặc n/2 + 2 nếu n lẻ. Ta dễ dàng tính được độ phức tạp thời gian của thuật toán là O(log n).

Tìm kiếm nhị phân (Binary search)

Bài toán nhị phân được phát biểu như sau:

Cho trước một dãy A được sắp xếp tăng dần, trả về vị trí của phần tử có giá trị x trong A.

Nếu duyệt hết tất cả các phần tử từ đầu đến cuối để tìm x trong giải thuật tìm kiếm tuần tự, ta sẽ mất thời gian là O(n).Tuy nhiên ta có thể lợi dụng tính chất mảng đã được sắp xếp để tìm kiếm với thời gian O(log n) với giải thuật tìm kiếm nhị phân.

Ý tưởng của thuật toán là liên tục chia không gian tìm kiếm thành hai nửa và loại bỏ đi một nửa. Thuật toán có thể trình bày như sau:

1. Không gian tìm kiếm S là một dãy con chứa các giá trị có thể là kết quả.

2. Ở mỗi bước, thuật toán so sánh giá trị cần tìm với phần tử chính giữa của không gian tìm kiếm. Dựa trên sự so sánh đó và ta đã biết dãy A đã sắp xếp, ta có thể loại bỏ một nửa số phần tử của dãy S. Lặp lại quá trình này, cuối cùng ta sẽ được một không gian tìm kiếm bao gồm một phần tử duy nhất.

3. Khi đó nếu phần tử duy nhất đó bằng x thì chỉ số của nó chính là nghiệm của bài toán. Nếu không bằng x thì phần tử x không tồn tại trong mảng.

Ví dụ: Tìm x = 55 trong mảng đã sắp xếp tăng dần {0, 5, 14, 17, 22, 31, 55, 68, 72, 81, 88} với chỉ 3 bước như sau:

Thuật toán sắp xếp nhanh (Quick Sort)

Quick Sort là một thuật toán sắp xếp nhanh và hiệu quả sử dụng phương pháp chia để trị. Nó hoạt động bằng cách chọn một phần tử chốt từ mảng và chia các phần tử còn lại thành hai mảng con, một mảng con chứa các phần tử nhỏ hơn hoặc bằng phần tử chốt và mảng con còn lại chứa các phần tử lớn hơn phần tử chốt. Bằng việc lặp lại các bước trên cho các mảng con ta sẽ thu được mảng đã được sắp xếp. 

Một lần chia mảng thành 2 mảng con có độ phức tạp là O(n). Trong điều kiện lý tưởng, phần tử chốt sẽ chia mảng lớn thành hai mảng con có độ dài bằng nhau. Như vậy sẽ có log(n) lần chia mảng. Nên độ phức tạp thuật toán là O(nlog(n)) trong điều kiện lý tưởng.

Ta sẽ minh họa cho thuật toán bằng cách sắp xếp mảng {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48} như sau:

Ưu nhược điểm 

Ưu điểm

Ưu điểm đầu tiên và cũng dễ nhận biết nhất của phương pháp chia để trị là nó giúp ta giải các bài toán khó. Ví dụ như bài toán tháp Hà Nội là một trò chơi giải đố toán học khó, nhưng với phương pháp chia để trị, nhờ việc chia bài toán thành các bài toán nhỏ hơn nó đã giải được một cách dễ dàng. 

Một ưu điểm khác của mô hình này, nó góp phần khám phá ra các thuật toán hiệu quả như Quick sort hay Merge sort. Nó sử dụng bộ nhớ cache một cách hiệu quả do khi bài toán con đủ đơn giản, chúng có thể được giải bên trong cache mà không phải truy cập bộ nhớ chính. Như trong bài toán sắp xếp nhanh, thay vì chia mảng thành các mảng con có 1 phần tử, thuật toán có thể kết hợp sắp xếp chèn cho mảng con có ít phần tử để sử dụng bộ nhớ cache hiệu quả hơn. Ngoài ra, việc tính toán một số bài toán con có thể thực hiện song song trên các bộ vi xử lý đa nhân, làm giảm thời gian tính toán một cách đáng kể. 

Nhược điểm

Một trong những vấn đề phổ biến của chia để trị là việc sử dụng đệ quy khi cài đặt thuật toán. Trong một số trường hợp, làm giảm đi các ưu thế của phương pháp này. Đầu tiên việc một hàm tự gọi chính nó trong đệ quy cần nhiều không gian bộ nhớ và việc cấp phát bộ nhớ làm giảm tốc độ thuật toán khi đệ quy. Tiếp theo, một bài toán có thể chia thành nhiều bài toán con, và một bài toán con có thể xuất hiện nhiều lần làm thuật toán kém hiệu quả như trong bài toán tính số Fibonacci thứ n sử dụng phương pháp chia đệ trị bằng đệ quy. 

Một nhược điểm khác của phương pháp này là việc cài đặt thuật toán bằng phương pháp chia để trị đôi khi phức tạp hơn đáng kể so với phương pháp lặp truyền thống. 

Kết luận

Như vậy chúng ta đã tìm hiểu phương pháp chia để trị qua một số bài toán phổ biến cũng như chỉ ra những ưu, nhược điểm của phương pháp này. Việc thiết kế các thuật toán sử dụng phương pháp thích hợp yêu cầu người lập trình phải có kiến thức rộng rãi về các phương pháp khác nhau. Trong bài viết sau, chúng ta sẽ tìm hiểu về các phương pháp khác cùng các bài toán thích hợp với chúng.