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

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

Trích từ trang web :

The recursion tree

To a beginner, the previous method won’t be very useful. To use it successfully we need to make a good guess – and to make a good guess we need some insight. The question is, how to gain this insight? Let’s take a closer look at what’s happening, when we try to evaluate the recurrence (or equivalently, when we run the corresponding recursive program).

We may describe the execution of a recursive program on a given input by a rooted tree. Each node will correspond to some instance of the problem the program solves. Consider an arbitrary vertex in our tree. If solving its instance requires recursive calls, this vertex will have children corresponding to the smaller subproblems we solve recursively. The root node of the tree is the input of the program, leaves represent small problems that are solved by brute force.

Now suppose we label each vertex by the amount of work spent solving the corresponding problem (excluding the recursive calls). Clearly the runtime is exactly the sum of all labels.

As always, we only want an asymptotic bound. To achieve this, we may “round” the labels to make the summation easier. Again, we will demonstrate this method on examples.

Example 4. The recursion tree for MergeSort on 5 elements.


The recursion tree for the corresponding recurrence equation. This time, the number inside each vertex represents the number of steps the algorithm makes there.


Note that in a similar way we may sketch the general form of the recursion tree for any recurrence. Consider our old friend, the equation (1). Here we know that there is a number c such that the number of operations in each node can be bound by (c times the current value of N). Thus the tree in the example below is indeed the worst possible case.

Example 5. A worst-case tree for the general case of the recurrence equation (1).


Now, the classical trick from combinatorics is to sum the elements in an order different from the order in which they were created. In this case, consider an arbitrary level of the tree (i.e. a set of vertices with the same depth). It is not hard to see that the total work on each of the levels is cN.

Now comes the second question: What is the number of levels? Clearly, the leaves correspond to the trivial cases of the algorithm. Note that the size of the problem is halved in each step. Clearly after lg N steps we are left with a trivial problem of size 1, thus the number of levels is $ \Theta$(log N).

Combining both observations we get the final result: The total amount of work done here is $ \Theta$(cN x log N) = $ \Theta$(Nlog N).

A side note. If the reader doesn’t trust the simplifications we made when using this method, he is invited to treat this method as a “way of making a good guess” and then to prove the result using the substitution method. However, with a little effort the application of this method could also be upgraded to a full formal proof.


Trả lờ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: Logo

Bạn đang bình luận bằng tài khoản Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

%d bloggers like this: