DAA - Chia rẽ & Chinh phục

Nhiều thuật toán có bản chất là đệ quy để giải quyết một vấn đề đã cho một cách đệ quy giải quyết các vấn đề con.

Trong divide and conquer approach, một vấn đề được chia thành các vấn đề nhỏ hơn, sau đó các vấn đề nhỏ hơn được giải quyết một cách độc lập, và cuối cùng các giải pháp của các vấn đề nhỏ hơn được kết hợp thành một giải pháp cho vấn đề lớn.

Nói chung, thuật toán chia để trị có ba phần:

Divide the problem thành một số vấn đề con là các trường hợp nhỏ hơn của cùng một vấn đề.
Conquer the sub-problemsbằng cách giải chúng một cách đệ quy. Nếu chúng đủ nhỏ, hãy giải các bài toán con dưới dạng trường hợp cơ sở.
Combine the solutions cho các vấn đề phụ thành giải pháp cho vấn đề ban đầu.

Ưu và nhược điểm của Phương pháp Tiếp cận Chia rẽ và Chinh phục

Phương pháp phân chia và chinh phục ủng hộ sự song song vì các vấn đề phụ là độc lập. Do đó, một thuật toán, được thiết kế bằng kỹ thuật này, có thể chạy đồng thời trên hệ thống đa xử lý hoặc trong các máy khác nhau.

Trong cách tiếp cận này, hầu hết các thuật toán được thiết kế bằng cách sử dụng đệ quy, do đó khả năng quản lý bộ nhớ rất cao. Đối với ngăn xếp hàm đệ quy được sử dụng, nơi trạng thái hàm cần được lưu trữ.