Nghiên cứu về độ phức tạp của thuật toán (phần 11)

· Thuật toán, Tin học, Uncategorized

Trích từ trang web : http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=complexity1

The Master Theorem

We already started to see a pattern here. Given a recurrence equation, take the corresponding recurrence tree and compute the amounts of work done on each level of the tree. You will get a geometric sequence. If it decreases, the total work is proportional to work done in the root node. If it increases, the total work is proportional to the number of leaves. If it remains the same, the total work is (the work done on one level) times (the number of levels).

Ta bắt đầu thấy một mô hình ở đây. Cho một phương trình đệ quy, có cây đệ quy tương ứng và tính toán lượng công việc thực hiện trên mỗi cấp độ của cây. Bạn sẽ nhận được một chuỗi hình học. Nếu nó giảm, tổng số công việc là tỷ lệ thuận với công việc thực hiện trong nút gốc. Nếu nó làm tăng, tổng số công việc là tỷ lệ thuận với số lượng lá. Nếu nó vẫn giữ nguyên, tổng số công việc là (công việc thực hiện trên một cấp độ) lần (số lượng các cấp).

Actually, there are a few ugly cases, but almost often one of these three cases occurs. Moreover, it is possible to prove the statements from the previous paragraph formally. The formal version of this theorem is known under the name Master Theorem.

Trên thực tế, có một vài trường hợp xấu xí, nhưng hầu như thường là một trong ba trường hợp xảy ra. Hơn nữa, nó có thể chứng minh các báo cáo từ các đoạn trước chính thức. Phiên bản chính thức của định lý này được biết đến dưới cái tên định lý chủ

For reference, we give the full formal statement of this theorem. (Note that knowing the formal proof is not necessary to apply this theorem on a given recurrence equation.)

Để tham khảo, chúng tôi cung cấp cho các phát biểu đầy đủ chính thức của định lý này. (Lưu ý rằng biết bằng chứng chính thức không cần thiết phải áp dụng định lý này trên một phương trình đệ quy nhất định.)

Let a $ \geq$ 1 and b > 1 be integer constants. Let p be a non-negative non-decreasing function. Let f be any solution of the recurrence equation

Cho một \ geq 1 và b> 1 là hằng số nguyên. Cho p là hàm không giảm không âm. Cho f bất kỳ nghiệm của phương trình đệ quy:

Then:

Khi đó:

  1. If  for some $ \varepsilon$ > 0 then 
  2. If , then f (N) = $ \Theta$(p(N)log N).
  3. If  for some $ \varepsilon$ > 0, and if ap(N/b$ \leq$ cp(N) for some c < 1 and for almost all N, then f (N) = $ \Theta$(p(N)).

Case 1 corresponds to our Example 7. Most of the time is spent making the recursive calls and it’s the number of these calls that counts.

Trường hợp 1 tương ứng với Ví dụ của chúng tôi 7. Phần lớn thời gian là chi tiêu làm cho các lời gọi đệ quy và đó là số lượng các lời gọi mà đếm được.

Case 2 corresponds to our Example 5. The time spent making the calls is roughly equal to the time to prepare the calls and process the results. On all levels of the recursion tree we do roughly the same amount of work, the depth of the tree is always logarithmic.

Trường hợp 2 tương ứng với Ví dụ của chúng tôi 5. Thời gian làm các cuộc gọi là tương đương với thời gian để chuẩn bị các cuộc gọi và xử lý kết quả. Trên tất cả các cấp của cây đệ quy, chúng tôi làm khoảng cùng một công việc, độ sâu của cây luôn luôn là logarit.

Case 3 corresponds to our Example 6. Most of the time is spent on preparing the recursive calls and processing the results. Usually the result will be asymptotically equal to the time spent in the root node.

Trường hợp 3 tương ứng với Ví dụ 6 của chúng tôi . Hầu hết thời gian được dành cho việc chuẩn bị các lời gọi đệ quy và xử lý kết quả. Thường kết quả sẽ tiệm cận bằng với thời gian dành cho nút gốc.

Note the word “usually” and the extra condition in Case 3. For this result to hold we need p to be somehow “regular” – in the sense that for each node in the recursion tree the time spent in the node must be greater than the time spent in its chidren (excluding further recursive calls). This is nothing to worry about too much, most probably all functions pyou will encounter in practice will satisfy this condition (if they satisfy the first condition of Case 3).

Lưu ý các từ “thông thường” và điều kiện thêm trong trường hợp 3. Đối với kết quả này để giữ chúng ta cần p là bằng cách nào đó “thường xuyên” – theo nghĩa là cho mỗi nút trong cây đệ quy các thời gian dành cho nút phải lớn hơn thời gian dành cho con của nó (trừ các lời gọi đệ quy hơn nữa). Điều này là không có gì phải lo lắng về quá nhiều, có lẽ hầu hết tất cả các hàm pyou sẽ gặp phải trong thực tế sẽ đáp ứng điều kiện này (nếu đáp ứng các điều kiện đầu tiên của Trường hợp 3).

Example 8. Let f (N) be the time Strassen’s fast matrix multiplication algorithm needs to multiply two N x N square matrices. This is a recursive algorithm, that makes 7 recursive calls, each time multiplying two (N/2) x (N/2) square matrices, and then computes the answer in $ \Theta$(N2) time.

Ví dụ 8. Cho f (N) là thời gian nhanh ma trận thuật toán Strassen nhân của cần nhân hai N x N ma trận vuông. Đây là một thuật toán đệ quy, mà làm cho 7 cuộc gọi đệ quy, mỗi lần nhân hai (N / 2) x (N / 2) các ma trận vuông, và sau đó tính toán câu trả lời trong \ Theta (N2) thời gian.

This leads us to the following recurrence equation:

Using the Master Theorem, we see that Case 1 applies. Thus the time complexity of Strassen’s algorithm is. Note that by implementing the definition of matrix multiplication we get only a $ \Theta$(N3)algorithm.

Bằng cách sử dụng định lý tổng thể, chúng ta thấy rằng Trường hợp 1 được áp dụng. Do đó độ phức tạp của thuật toán Strassen là . Lưu ý rằng bằng cách thực hiện các định nghĩa của phép nhân ma trận, ta chỉ nhận được một \ Theta (N3) thuật toán.

Example 9. Occasionally we may encounter the situation when the problems in the recursive calls are not of the same size. An example may be the “median-of-five” algorithm to find the k-th element of an array. It can be shown that its time complexity satisfies the recurrence equation

Ví dụ 9. Thỉnh thoảng ta có thể gặp tình huống khi các bài toán trong lời gọi đệ quy là không có cùng kích thước. Một ví dụ có thể là “trung bình-của-năm” thuật toán để tìm các phần tử thứ k của mảng. Có thể chỉ ra rằng độ phức tạp thời gian của thuật toán thỏa mãn phương trình đệ quy:

How to solve it? Can the recursion tree be applied also in such asymmetric cases? Is there a more general version of Master Theorem that handles also these cases? And what should I do with the recurrence f (N) = 4f (N/4) + $ \Theta$(Nlog N), where the Master Theorem doesn’t apply?

Làm thế nào để giải quyết nó? Cây đệ quy có thể được áp dụng trong các trường hợp bất đối xứng như vậy? Có một tổng quát hơn của Định lý chủ mà cũng xử lý những trường hợp này? Và những gì tôi nên làm gì với đệ quy f (N) = 4f (N / 4) + \ Theta (nLog N), nơi mà các định lý chủ không áp dụng?

We won’t answer these questions here. This article doesn’t claim to be the one and only reference to computational complexity. If you are already asking these questions, you understand the basics you need for programming contests – and if you are interested in knowing more, there are good books around that can help you.

Tôi sẽ không trả lời những câu hỏi này ở đây. Bài viết này không yêu cầu bồi thường là một và chỉ tham chiếu đến phức tạp tính toán. Nếu bạn định hỏi những câu hỏi đó, bạn chắc đã hiểu những điều cơ bản bạn cần cho các cuộc thi lập trình – và nếu bạn muốn biết thêm, có những cuốn sách tốt xung quanh có thể giúp bạn.

Thanks for reading this far. If you have any questions, comments, bug reports or any other feedback, please use the Round tables. I’ll do my best to answer.

Cám ơn bạn đã đọc đến đây. Nếu bạn có bất kỳ câu hỏi, ý kiến, báo cáo lỗi hoặc bất kỳ thông tin phản hồi khác, tôi sẽ làm hết sức mình để trả lời !

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

%d bloggers like this: