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

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

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

Divide&conquer using recursion

From the previous example we could get the feeling that recursion is evil and leads to horribly slow programs. The contrary is true. Recursion can be a very powerful tool in the design of effective algorithms. The usual way to create an effective recursive algorithm is to apply the divide&conquer paradigm – try to split the problem into several parts, solve each part separately and in the end combine the results to obtain the result for the original problem. Needless to say, the “solve each part separately” is usually implemented using recursion – and thus applying the same method again and again, until the problem is sufficiently small to be solved by brute force.

Example 3. The sorting algorithm MergeSort described in pseudocode.

MergeSort(sequence S) {
  if (size of S <= 1) return S;
  split S into S_1 and S_2 of roughly the same size;
  MergeSort(S_1);
  MergeSort(S_2);
  combine sorted S_1 and sorted S_2 to obtain sorted S;
  return sorted S;
}

Clearly O(N) time is enough to split a sequence with N elements into two parts. (Depending on the implementation this may be even possible in constant time.) Combining the shorter sorted sequences can be done in $ \Theta$(N): Start with an empty S. At each moment the smallest element not yet in S is either at the beginning of S1 or at the beginning of S2. Move this element to the end of S and continue.

Thus the total time to MergeSort a sequence with N elements is $ \Theta$(N) plus the time needed to make the two recursive calls.

Let f (N) be the time complexity of MergeSort as defined in the previous part of our article. The discussion above leads us to the following equation:

where p is a linear function representing the amount of work spent on splitting the sequence and merging the results.

Basically, this is just a recurrence equation. If you don’t know this term, please don’t be afraid. The word “recurrence” stems from the latin phrase for “to run back”. Thus the name just says that the next values of f are defined using the previous (i.e. smaller) values of f.

Well, to be really formal, for the equation to be complete we should specify some initial values – in this case, f (1). This (and knowing the implementation-specific function p) would enable us to compute the exact values of f.

But as you hopefully understand by now, this is not necessarily our goal. While it is theoretically possible to compute a closed-form formula for f (N), this formula would most probably be really ugly… and we don’t really need it. We only want to find a $ \Theta$-bound (and sometimes only an O-bound) on the growth of f. Luckily, this can often be done quite easily, if you know some tricks of the trade.

As a consequence, we won’t be interested in the exact form of p, all we need to know is that p(N) = $ \Theta$(N). Also, we don’t need to specify the initial values for the equation. We simply assume that all problem instances with small N can be solved in constant time.

The rationale behind the last simplification: While changing the initial values does change the solution to the recurrence equation, it usually doesn’t change its asymptotic order of growth. (If your intuition fails you here, try playing with the equation above. For example fix p and try to compute f (8), f (16) and f (32) for different values of f(1).)

If this would be a formal textbook, at this point we would probably have to develop some theory that would allow us to deal with the floor and ceiling functions in our equations. Instead we will simply neglect them from now on. (E.g. we can assume that each division will be integer division, rounded down.)

A reader skilled in math is encouraged to prove that if p is a polynomial (with non-negative values on N) and q(n) =p(n + 1) then q(n) = $ \Theta$(p(n)). Using this observation we may formally prove that (assuming the f we seek is polynomially-bounded) the right side of each such equation remains asymptotically the same if we replace each ceiling function by a floor function.

The observations we made allow us to rewrite our example equation in a more simple way:

(1)

Note that this is not an equation in the classical sense. As in the examples in the first part of this article, the equals sign now reads “is asymptotically equal to”. Usually there are lots of different functions that satisfy such an equation. But usually all of them will have the same order of growth – and this is exactly what we want to determine. Or, more generally, we want to find the smallest upper bound on the growth of all possible functions that satisfy the given equation.

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: