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

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

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

In the last sections of this article we will discuss various methods of solving these “equations”. But before we can do that, we need to know a bit more about logarithms.

Notes on logarithms

By now, you may have already asked one of the following questions: If the author writes that some complexity is e.g.O(N log N), what is the base of the logarithm? In some cases, wouldn’t O(N log2N) be a better bound?

The answer: The base of the logarithm does not matter, all logarithmic functions (with base > 1) are asymptotically equal. This is due to the well-known equation:

(2)

 

Note that given two bases a, b, the number 1/logba is just a constant, and thus the function logaN is just a constant multiple of logbN.

To obtain more clean and readable expressions, we always use the notation log N inside big-Oh expressions, even if logarithms with a different base were used in the computation of the bound.

By the way, sadly the meaning of log N differs from country to country. To avoid ambiguity where it may occur: I uselog N to denote the decadic (i.e. base-10) logarithm, ln N for the natural (i.e. base-e) logarithm, lg N for the binary logarithm and logbN for the general case.

 

 

 

Now we will show some useful tricks involving logarithms, we will need them later. Suppose a, b are given constants such that ab > 1.

From (2) we get:

 

Using this knowledge, we can simplify the term  as follows:

(3)

 

The substitution method

This method can be summarized in one sentence: Guess an asymptotic upper bound on f and (try to) prove it by induction.

As an example, we will prove that if f satisfies the equation (1) then f (N) = O(N log N).

From (1) we know that

 

for some c. Now we will prove that if we take a large enough (but constant) d then for almost all N we have f (N$ \leq$dN lg N. We will start by proving the induction step.

Assume that f (N/2) $ \leq$ d (N/2)lg(N/2). Then

 

In other words, the induction step will hold as long as d > c. We are always able to choose such d.

We are only left with proving the inequality for some initial value N. This gets quite ugly when done formally. The general idea is that if the d we found so far is not large enough, we can always increase it to cover the initial cases.

Note that for our example equation we won’t be able to prove it for N = 1, because lg 1 = 0. However, by taking d > 2(f (1) + f (2) + f (3) + c) we can easily prove the inequality for N = 2 and N = 3, which is more than enough.

Please note what exactly did we prove. Our result is that if f satisfies the equation (1) then for almost all N we have f(N$ \leq$ dN lg N, where d is some fixed constant. Conclusion: from (1) it follows that f (N) = O(N lg N).

 

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: