Chapter 1 Introduction Algorithms and problems An algorithm
Proof. See the textbook. Omitted. Example 11
Download 428.46 Kb.
|
- Navigate this page:
- The Complexity of Problems
- Complexity of a problem
Proof. See the textbook. Omitted. Example 11 Obtain an asymptotic bound for the following recurrence relations using the master theorem. T(n) = 9T(n/3) + n T(n) =T(2n/3) +1 T(n) = 3T(n/4) + nlgn. Solution: T(n) = 9T(n/3) + n lgba = lg39 = 2. Set e = 0.5. We have f(n) = n = O(n2-0.5)= O(n1.5). Therefore, T(n) = Q (n2). T(n) =T(2n/3) +1 lgba = lg3/21 = 0. Since n0 = 1, the first rule in the Master Theorem is not applicable, but second rule can be applied. Therefore, T(n) = Q (n0lgn) = Q (lgn).
T(n) = 3T(n/4) + nlgn lgba = lg43 = 0.793. Obviously, the first two rules of the Master Theorem do not apply. We check the third rule. Setting e = 0.1, we have f(n) = nlgn = (n) = (  ).
Moreover, we have af(n/b) = 3(n/4)lg(n/4) ≤ (3/4)nlgn for any n > 1. If we set c = 3/4, we will have, for any n > 1, af(n/b) ≤ (3/4)nlgn = cf(n). Therefore, by the Master Theorem, T(n) = Q(nlgn). The Complexity of Problems We notice that some problems are easier to solve, some are harder, and some are very difficult or even not solvable. For a given problem we wish to know how hard the problem is. When we have designed an algorithm, we also wish to know if we can do better, or if we have reached the bottom. For example, it is well-known that any comparison-based sorting algorithm needs at least lgn! comparisons to sort n numbers. Therefore, this result save researchers a lot of efforts and time to search for a better algorithm which will never be obtained. We define the Complexity of a problem to be the minimum time required to solve this problem. Obtaining a complexity lower bound for a given problem is often an important topic. An algorithm is called optimal if its time complexity matches with the problem lower bound. But, before you can claim your algorithm is optimal you need to obtain its lower bound. We will discuss some techniques and results on this issue. There are many difficult problems whose complexities are not known. For those problems, the best known algorithm needs an exponential time. A problem is called tractable if it can be solved in polynomial time, otherwise, intractable. Because the exponential function grows much faster than any polynomial function, we would like to draw a line between these two classes of functions. A problem that can be solved in polynomial time is said to belong to class P. There is a class of problems whose tractability is not known. What we know is that they can be solved by a non-deterministic computer in polynomial time. Problems that can be solved by a non-deterministic computer in polynomial time are said to belong to class NP. Class P is a subset of class NP. The NP-completeness theory has been developed to characterize those NP problems for witch no polynomial time algorithm is known so far. Moreover, if any of them can be solved some day in polynomial time, then all NP problems can be solved in polynomial time. Those problems are said to belong to NP-complete class. Obviously, if any NP-complete problem is proven to be not polynomial solvable, then all problems in NP-complete class are not polynomial solvable. We will discuss the NP-complete problems and how to prove a problem to be in this class in Chapter 34. End of Ch. 1. Download 428.46 Kb. Share with your friends:
|