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

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

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

More recursion trees

By now you should be asking: Was it really only a coincidence that the total amount of work on each of the levels in Example 5 was the same?

The answer: No and yes. No, there’s a simple reason why this happened, we’ll discover it later. Yes, because this is not always the case – as we’ll see in the following two examples.

Example 6. Let’s try to apply our new “recursion tree” method to solve the following recurrence equation:

 

The recursion tree will look as follows:

 

Let’s try computing the total work for each of the first few levels. Our results:

 

level 1 2 3
work cN3 $ {3\over 8}$cN3 $ {3^2 \over 8^2}$cN3

Clearly as we go deeper in the tree, the total amount of work on the current level decreases. The question is, how fast does it decrease? As we move one level lower, there will be three times that many subproblems. However, their size gets divided by 2, and thus the time to process each of them decreases to one eighth of the original time. Thus the amount of work is decreased by the factor 3/8.

But this means that the entries in the table above form a geometric progression. For a while assume that this progression is infinite. Then its sum would be

 

Thus the total amount of work in our tree is $ \Omega$(N3) (summing the infinite sequence gives us an upper bound). But already the first element of our progression is $ \Theta$(N3). It follows that the total amount of work in our tree is $ \Theta$(N3) and we are done.

The important generalization of this example: If the amounts of work at subsequent levels of the recursion tree form adecreasing geometric progression, the total amount of work is asymptotically the same as the amount of work done in the root node.

From this result we can deduce an interesting fact about the (hypothetical) algorithm behind this recurrence equation: The recursive calls didn’t take much time in this case, the most time consuming part was preparing the recursive calls and/or processing the results. (I.e. this is the part that should be improved if we need a faster algorithm.)

Example 7. Now let’s try to apply our new “recursion tree” method to solve the following recurrence equation:

 

The recursion tree will look as follows:

 

Again, let’s try computing the total work for each of the first few levels. We get:

 

level 1 2 3
work cN $ {5\over 3}$cN $ {5^2 \over 3^2}$cN

This time we have the opposite situation: As we go deeper in the tree, the total amount of work on the current level increases. As we move one level lower, there will be five times that many subproblems, each of them one third of the previous size, the processing time is linear in problem size. Thus the amount of work increased by the factor 5/3.

Again, we want to compute the total amount of work. This time it won’t be that easy, because the most work is done on the lowest level of the tree. We need to know its depth.

The lowest level corresponds to problems of size 1. The size of a problem on level k is N/3k. Solving the equation 1 =N/3k we get k = log3N. Note that this time we explicitly state the base of the logarithm, as this time it will be important.

Our recursion tree has log3N levels. Each of the levels has five times more vertices than the previous one, thus the last level has  levels. The total work done on this level is then .

Note that using the trick (3) we may rewrite this as .

Now we want to sum the work done on all levels of the tree. Again, this is a geometric progression. But instead of explicitly computing the sum, we now reverse it. Now we have a decreasing geometric progression…and we are already in the same situation as in the previous example. Using the same reasoning we can show that the sum is asymptotically equal to the largest element.

It follows that the total amount of work in our tree is  and we are done.

Note that the base-3 logarithm ends in the exponent, that’s why the base is important. If the base was different, also the result would be asymptotically different.

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: