Trong hướng dẫn này, bạn sẽ tìm hiểu cách hoạt động của thuật toán chia và chinh phục. Chúng tôi cũng sẽ so sánh cách tiếp cận chia và chinh phục với các cách tiếp cận khác để giải quyết một bài toán đệ quy.
Một thuật toán chia để trị là một chiến lược giải quyết một vấn đề lớn bởi
- chia vấn đề thành các vấn đề phụ nhỏ hơn
- giải quyết các vấn đề phụ và
- kết hợp chúng để có được đầu ra mong muốn.
Để sử dụng thuật toán chia và chinh phục, đệ quy được sử dụng. Tìm hiểu về đệ quy trong các ngôn ngữ lập trình khác nhau:
- Đệ quy trong Java
- Đệ quy trong Python
- Đệ quy trong C ++
Các thuật toán phân chia và chinh phục hoạt động như thế nào?
Dưới đây là các bước liên quan:
- Chia : Chia bài toán đã cho thành các bài toán con bằng cách sử dụng đệ quy.
- Chinh phục : Giải các bài toán con nhỏ hơn một cách đệ quy. Nếu bài toán con đủ nhỏ, hãy giải nó trực tiếp.
- Kết hợp: Kết hợp các giải pháp của các 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ế.
Hãy để chúng tôi hiểu khái niệm này với sự trợ giúp của một ví dụ.
Ở đây, chúng ta sẽ sắp xếp một mảng bằng cách sử dụng phương pháp chia và chinh phục (tức là sắp xếp hợp nhất).
- Cho mảng đã cho là:
Mảng để hợp nhất sắp xếp - Chia mảng thành hai nửa.
Chia mảng thành hai phần con
Một lần nữa, chia đệ quy mỗi phần con thành hai nửa cho đến khi bạn nhận được các phần tử riêng lẻ.
Chia mảng thành các phần con nhỏ hơn - Bây giờ, hãy kết hợp các phần tử riêng lẻ theo cách được sắp xếp. Tại đây, hãy chinh phục và kết hợp các bước đi song song với nhau.
Kết hợp các phần con
Thời gian phức tạp
Độ phức tạp của thuật toán chia và giải được tính bằng cách sử dụng định lý chính.
T (n) = aT (n / b) + f (n), trong đó, n = kích thước của đầu vào a = số bài toán con trong đệ quy n / b = kích thước của mỗi bài toán con. Tất cả các bài toán con được giả định có cùng kích thước. f (n) = chi phí của công việc được thực hiện bên ngoài lệnh gọi đệ quy, bao gồm chi phí phân chia vấn đề và chi phí hợp nhất các giải pháp
Chúng ta hãy lấy một ví dụ để tìm độ phức tạp về thời gian của một bài toán đệ quy.
Đối với sắp xếp hợp nhất, phương trình có thể được viết dưới dạng:
T (n) = aT (n / b) + f (n) = 2T (n / 2) + O (n) Trong đó, a = 2 (mỗi lần, một bài toán được chia thành 2 bài toán con) n / b = n / 2 (kích thước của mỗi bài toán con là một nửa đầu vào) f (n) = thời gian thực hiện để chia bài toán và gộp các bài toán con T (n / 2) = O (n log n) (Để hiểu điều này, vui lòng tham khảo định lý chính.) Bây giờ, T (n) = 2T (n log n) + O (n) ≈ O (n log n)
Phân chia và chinh phục Vs Phương pháp năng động
Cách tiếp cận phân chia và chinh phục chia một vấn đề thành các bài toán con nhỏ hơn; các bài toán con này tiếp tục được giải một cách đệ quy. Kết quả của mỗi bài toán con không được lưu trữ để tham khảo trong tương lai, ngược lại, trong cách tiếp cận động, kết quả của mỗi bài toán con được lưu trữ để tham khảo trong tương lai.
Sử dụng phương pháp chia để trị khi cùng một bài toán con không được giải nhiều lần. Sử dụng phương pháp tiếp cận động khi kết quả của một bài toán con sẽ được sử dụng nhiều lần trong tương lai.
Hãy để chúng tôi hiểu điều này với một ví dụ. Giả sử chúng ta đang cố gắng tìm chuỗi Fibonacci. Sau đó,
Cách tiếp cận Phân chia và Chinh phục:
fib (n) Nếu n <2, trả về 1 Khác, trả về f (n - 1) + f (n -2)
Cách tiếp cận năng động:
mem = () fib (n) If n in mem: return mem (n) else, If n <2, f = 1 else, f = f (n - 1) + f (n -2) mem (n) = f trở lại f
Trong cách tiếp cận động, mem lưu trữ kết quả của mỗi bài toán con.
Ưu điểm của Thuật toán Chia và Chinh phục
- Độ phức tạp đối với phép nhân hai ma trận bằng phương pháp ngây thơ là O (n 3 ), trong khi sử dụng cách tiếp cận chia và chinh phục (tức là phép nhân ma trận Strassen) là O (n 2,8074 ). Cách tiếp cận này cũng đơn giản hóa các vấn đề khác, chẳng hạn như Tháp Hà Nội.
- Cách tiếp cận này phù hợp với các hệ thống đa xử lý.
- Nó sử dụng hiệu quả bộ nhớ đệm.
Ứng dụng Phân chia và Chinh phục
- Tìm kiếm nhị phân
- Hợp nhất Sắp xếp
- Sắp xếp nhanh chóng
- Phép nhân ma trận Strassen
- Thuật toán Karatsuba
