lý Thạc sĩ Hiểu

Question

dạng Generic: T(n) = aT(n/b) + f(n)

Vì vậy, tôi phải so sánh n^logb (a) với f (n)

nếu n^logba>f(n) là trường hợp 1 và T(n)=Θ(n^logb(a))

nếu n^logba < f(n) là trường hợp 2 và T(n)=Θ((n^logb(a))(logb(a)))

Điều đó có đúng không? Hay tôi hiểu lầm điều gì đó?

Còn trường hợp 3 thì sao? Khi áp dụng?

Answer 1

Tôi nghĩ bạn đã hiểu lầm điều đó. nếu n^logba> f (n) là trường hợp 1 và T (n) = Θ (n^logb (một))

Ở đây bạn không nên lo lắng về f (n) là kết quả mà bạn đang nhận được là T (n) = Θ (n^logb (a)). f (n) là một phần của T (n) ..và nếu bạn nhận được kết quả T (n) thì giá trị đó sẽ bao gồm f (n). vì vậy, Không cần phải xem xét phần đó.

Hãy cho tôi biết nếu bạn không rõ ràng.

Answer 2

Lưu ý: Tôi hiểu rằng đã quá muộn để trả lời câu hỏi này. Tôi chỉ đưa nó vào đây để các thế hệ tương lai :)

Thạc sĩ Định lý cho tái phát Giải quyết

tái phát xảy ra trong một chia để trị chiến lược giải quyết vấn đề phức tạp.

Điều gì giải quyết?

• Nó giải quyết sự tái diễn của biểu mẫu T (n) = aT (n/b) + f (n).
• a phải lớn hơn hoặc bằng 1. Điều này có nghĩa là vấn đề ít nhất được giảm xuống một vấn đề nhỏ hơn một lần. Cần ít nhất một đệ quy
• b phải lớn hơn 1. Điều này có nghĩa là ở mỗi lần đệ quy, kích thước của sự cố được giảm xuống kích thước nhỏ hơn. Nếu b không lớn hơn 1, điều đó có nghĩa là các vấn đề phụ của chúng ta không có kích thước nhỏ hơn.
• f (n) phải dương cho các giá trị tương đối lớn hơn của n.

Hãy xem xét những hình ảnh dưới đây:

phép nói rằng chúng tôi có một vấn đề về kích thước n để được giải quyết. Tại mỗi bước, vấn đề có thể được chia thành một vấn đề phụ và mỗi vấn đề phụ có kích thước nhỏ hơn, trong đó kích thước được giảm xuống bằng hệ số b.

Tuyên bố trên theo các từ đơn giản có nghĩa là một vấn đề về kích thước n có thể được chia thành các vấn đề phụ với kích thước tương đối nhỏ hơn n/b.

Ngoài ra, biểu đồ trên cho thấy rằng ở cuối khi chúng tôi đã chia các vấn đề nhiều lần, mỗi vấn đề phụ sẽ nhỏ đến nỗi nó có thể được giải quyết trong thời gian không đổi.

Đối với nguồn gốc bên dưới xem xét log đến cơ sở b

Chúng ta hãy nói rằng H là chiều cao của cây, sau đó H = logn. Số lượng lá = a^logn.

• Tổng số công việc thực hiện ở cấp độ 1: f (n)
• Tổng số công việc được thực hiện tại Cấp độ 2: a * f (n/b)
• Tổng số công việc thực hiện ở cấp độ 1: a * a * f (n/b2)
• Tổng số công việc được thực hiện ở Cấp cuối cùng: số lá * θ (1). Đây tương đương với n^Loga

Ba trường hợp của Master lý

Trường hợp 1: Bây giờ chúng ta giả định rằng chi phí của hoạt động đang tăng lên bởi một yếu tố quan trọng ở mỗi cấp và bởi thời gian chúng ta đạt tới mức lá, giá trị của f (n) trở nên nhỏ hơn đa thức so với giá trị n^loga. Sau đó, thời gian chạy tổng thể sẽ bị chi phối nhiều bởi chi phí của cấp độ cuối cùng. Do đó T (n) = θ (n^loga)

Trường hợp 2: Giả sử chi phí hoạt động trên mỗi cấp là bằng nhau. Trong trường hợp đó f (n) xấp xỉ bằng n^loga. Do đó, tổng thời gian chạy sẽ là f (n) lần tổng số cấp độ. T (n) = θ (n^loga * logn) trong đó k có thể> = 0. Nơi logn sẽ là chiều cao của một cây cho k> = 0

Trường hợp 3: Chúng ta hãy giả định rằng chi phí của các hoạt động trên mỗi cấp được giảm một yếu tố quan trọng ở mỗi cấp và do thời gian chúng tôi đạt đến mức lá, giá trị của f (n) trở nên đa thức lớn hơn giá trị n^loga. Sau đó, thời gian chạy tổng thể sẽ bị chi phối nhiều bởi chi phí của cấp độ đầu tiên. Do đó T (n) = θ (f (n))

Nếu bạn quan tâm đến việc đọc chi tiết hơn và có lẽ một số ví dụ để thực hành. Bạn luôn có thể truy cập vào mục nhập blog của tôi cho cùng một. Master Method to Solve Recurrences