Tại sao thuật toán phân chia và chinh phục thường chạy nhanh hơn so với lực lượng vũ phu? Ví dụ: để tìm cặp điểm gần nhất. Tôi biết bạn có thể chỉ cho tôi bằng chứng toán học. Nhưng bằng trực giác, tại sao điều này lại xảy ra? Ma thuật?Tại sao thuật toán phân chia và chinh phục thường chạy nhanh hơn sức mạnh vũ phu?
Về mặt lý thuyết, có đúng là "phân chia và chinh phục luôn tốt hơn sức mạnh vũ phu"? Nếu không, có bất kỳ counterexample nào không?
Đối với câu hỏi đầu tiên của bạn, trực giác đằng sau phân chia và chinh phục là trong nhiều vấn đề, số lượng công việc phải được thực hiện dựa trên một số thuộc tính tổ hợp của đầu vào có tỷ lệ lớn hơn tuyến tính. Ví dụ, trong cặp vấn đề điểm gần nhất, thời gian chạy câu trả lời brute-force được xác định bởi thực tế là bạn phải xem xét tất cả các cặp điểm (O).
Nếu bạn lấy thứ gì đó phát triển bậc hai và cắt thành hai phần, mỗi phần có kích thước bằng một nửa so với trước, phải mất một phần tư thời gian đầu để giải quyết vấn đề trong mỗi nửa, để giải quyết vấn đề ở cả hai một nửa mất khoảng một nửa thời gian cần thiết cho giải pháp lực lượng vũ phu. Cắt nó thành bốn mảnh sẽ mất một phần tư thời gian, cắt nó thành tám miếng một phần tám thời gian, vv
Phiên bản đệ quy kết thúc nhanh hơn trong trường hợp này bởi vì ở mỗi bước, chúng ta tránh làm rất nhiều làm việc để đối phó với các cặp yếu tố bằng cách đảm bảo rằng không có quá nhiều cặp mà chúng ta thực sự cần phải kiểm tra. Hầu hết các thuật toán có giải pháp phân chia và chinh phục sẽ nhanh hơn vì lý do tương tự.
Đối với câu hỏi thứ hai của bạn, không, phân chia và chinh phục các thuật toán không nhất thiết phải nhanh hơn thuật toán brute-force. Xem xét vấn đề tìm giá trị lớn nhất trong một mảng. Thuật toán brute-force mất thời gian O (n) và sử dụng không gian O (1) vì nó thực hiện quét tuyến tính trên dữ liệu. Thuật toán phân chia và conquer được cung cấp tại đây:
này đòi hỏi thời gian O (n) là tốt, nhưng sử dụng O (log n) bộ nhớ cho không gian ngăn xếp. Nó thực sự tồi tệ hơn so với thuật toán tuyến tính đơn giản.
Ví dụ khác, maximum single-sell profit problem có giải pháp phân chia và chinh phục, nhưng giải pháp lập trình động được tối ưu hóa nhanh hơn trong cả thời gian và bộ nhớ.
Hy vọng điều này sẽ hữu ích!
Tôi khuyên bạn nên đọc qua chương 5 của Thiết kế Thuật toán, nó giải thích việc phân chia và chinh phục rất tốt.
Bằng trực giác, nếu có vấn đề, nếu bạn có thể chia thành hai vấn đề phụ với cùng mẫu với gốc, và độ phức tạp thời gian để hợp nhất kết quả của hai vấn đề phụ vào kết quả cuối cùng , sau đó nó nhanh hơn giải quyết vấn đề hoàn chỉnh orignal bởi brute-force.
Như đã nói trong Thuật toán Thiết kế, bạn thực sự không thể đạt được quá nhiều từ chia-và-chinh phục về thời gian, nói chung bạn chỉ có thể giảm thời gian phức tạp từ đa thức cao hơn để giảm đa thức (ví dụ từ O (n^3) đến O (n^2)), nhưng hầu như không từ hàm mũ đến hàm đa thức (ví dụ từ O (2^n) đến O (n^3)).
Tôi nghĩ rằng phần lớn bạn có thể đạt được từ phân chia và chinh phục là suy nghĩ để giải quyết vấn đề. Nó luôn luôn là một nỗ lực tốt để phá vỡ vấn đề lớn ban đầu xuống nhỏ hơn và dễ dàng hơn các vấn đề phụ. Ngay cả khi bạn không có thời gian chạy tốt hơn, nó vẫn giúp bạn suy nghĩ kỹ về vấn đề này.
Để chia sẻ bánh thành 16 miếng, giải pháp đầu tiên là cố gắng cắt 1/16 bánh và vân vân ... khó. Một giải pháp khác là cắt bánh trong 2, sau đó trong 2 lần nữa, sau đó mỗi của 1/4 trong 2, và mỗi 1/8 trong 2. –