Định lý tổng thể nâng cao về chia và chinh phục các định kỳ

Phân chia và chinh phục là một thuật toán hoạt động trên mô hình dựa trên bài toán phân nhánh đệ quy thành nhiều bài toán con cùng loại có thể được giải quyết một cách dễ dàng.

Ví dụ

Hãy lấy một ví dụ để tìm hiểu thêm về kỹ thuật chia và chinh phục -

function recursive(input x size n)
   if(n < k)
      Divide the input into m subproblems of size n/p.
      and call f recursively of each sub problem
   else
      Solve x and return

Kết hợp kết quả của tất cả các bài toán con và trả lại lời giải cho bài toán ban đầu.

Giải thích - Trong bài toán trên, vấn đề đặt ra là phải chia nhỏ thành các bài toán con nhỏ hơn để có thể giải quyết một cách dễ dàng.

Định lý Bậc thầy về chia và trị là một định lý phân tích có thể được sử dụng để xác định giá trị lớn-0 cho các thuật toán quan hệ đệ quy. Nó được sử dụng để tìm thời gian theo yêu cầu của thuật toán và biểu diễn nó ở dạng ký hiệu tiệm cận.

Ví dụ về giá trị thời gian chạy của bài toán trong ví dụ trên -

T(n) = f(n) + m.T(n/p)

Đối với hầu hết các thuật toán đệ quy, bạn sẽ có thể tìm thấy độ phức tạp về thời gian Đối với thuật toán sử dụng định lý bậc thầy, nhưng có một số trường hợp định lý bậc thầy có thể không áp dụng được. Đây là những trường hợp không áp dụng được định lý bậc thầy. Khi bài toán T (n) không đơn điệu, chẳng hạn, T (n) =sin n. Vấn đề hàm f (n) không phải là một đa thức.

Vì định lý tổng thể để tìm độ phức tạp thời gian không hiệu quả trong những trường hợp này, và định lý tổng thể nâng cao cho phép lặp đệ quy đã được thiết kế. Nó được thiết kế để xử lý vấn đề lặp lại của biểu mẫu -

T(n) = aT(n/b) + ø((n^k)logpn)

Trong đó n là quy mô của vấn đề.

a =số bài toán con trong đệ quy, a> 0

n / b =kích thước của mỗi bài toán con b> 1, k> =0 và p là một số thực.

Để giải quyết loại vấn đề này, chúng tôi sẽ sử dụng các giải pháp sau,

• Nếu a> b _k , thì T (n) =∅ (nlogba)
• Nếu a =b _k , sau đó
  • Nếu p> -1, thì T (n) =∅ (nlogba log ^{p + 1} n)
  • Nếu p =-1 thì T (n) =∅ (nlog _ba loglogn)
  • Nếu p <-1 thì T (n) =∅ (nlog _ba )
• Nếu a k , sau đó
  • Nếu p> =0, thì T (n) =∅ (n _k nhật ký _p n)
  • Nếu p <0, thì T (n) =∅ (nk)