Chapter 1 Introduction Algorithms and problems An algorithm
How to analyze the complexity of an algorithm
Download 428.46 Kb.
|
- Navigate this page:
- Example 7. Procedure
- The worst case, best case, and average case analysis
- Recurrence Relations
- The substitution method
- Note.
- The summation method and recursion-tree method The summation method is demonstrated by the following example. Example 10.
- The Ma s ter method
How to analyze the complexity of an algorithmAs we have discussed earlier, we use the total number of operations used by an algorithm as the time complexity. If we consider the asymptotic complexity, we can further simplify our analysis. We only need to count the number times the major operation will be executed. The major operation is the one that is executed most often. Example 7. Procedure Linear search (x, A[1..n]) Input: number x and array A of n numbers Ourput: index i if A[i] = x, 0 otherwise.
i 1 while (i ≤ n and x ≠ A[i]) do i i + 1 if i ≤ n then return (i) else return (0) End The major operations in the procedure are the comparisons between x and elements of A. As we can see that the number of such comparisons is at most n. Therefore, the time complexity is T(n) = O(n). The reason behind this is that there are only a small constant number of different kinds of operations in any algorithm. The commonly used operations include additions, subtractions, multiplications, divisions, data movements, pointer settings, comparisons, and so on. The number of different operations used by an algorithm is a small constant. Suppose there are c different operations, O1, O2, …, Oc, where O1 is the major operation. Let Oj be executed nj times. 1 ≤ j ≤ c. Then the total number of operations =  ≤ c n1.
Also, we assume different operations require an equal amount of time to finish. This assumption is valid from asymptotic point of view. (For example, the multiplication may needs 10 times more time than the addition, but the 10 is only a small constant.) Therefore, T(n) = O(n1). Note. A little care must be taken. The pseudo code may contain some operations that are not basic operations. For example, if the pseudo code contains an operation of x n! or z Min {A[1], A[2], …, A[n]} We cannot consider any of them as a single operation because they represent a single step, not a single operation. Such a step itself needs many operations depending on the size of n. We need to analyze how many basic operations to implement them first, and then add to the total number of basic operations. The integer n itself is treated as a regular variable although it is arguable assumption when n . The worst case, best case, and average case analysis Look at the linear search algorithm. Given an array of n numbers and a number x, if x = A[1], then we are lucky and the algorithm will quickly produce the result. However, if x is not contained in this array, then the algorithm needs n comparisons, which represents the worst case. Therefore, the worst case analysis is to get a upper bound on the number of operations the algorithm requires even in the most difficult case. For the linear search algorithm, it is O(n). The best case analysis is to get an estimate on the minimum number of operations required by the algorithm in most lucky case. In the case of linear search, it is O(1). The average case analysis is to get an estimate on the average number of operations the algorithm may require over all possible sets of input values. If we assume the x is contained in the array A and has an equal probability 1/n to be A[i], 1 ≤ i ≤ n, then the average complexity of the linear search is (1 + 2 + … + n) / n = (n+1)/2 = O(n). Usually, we need to know the distribution of all possible sets of input values for the average analysis. The main focus of this book is on the worst case analysis. Recurrence Relations In this section, we will not present a general discussion on recurrence relations. The general discussion can be found in many discrete mathematics books. We focus on a special form of recurrence relation: T(n) = aT(n/b) + f(n) T(1) = (1) where a and b are two constants. We often derive to the above relation when we use divide-conquer method to solve a problem. We introduce several approaches to solving this relation. The substitution method This method consists of two steps: Guess a form of solution Using mathematical induction to prove that this form is valid. Example 8. Solve the following recurrence relation: T(n) = 2T(n/2) + n. Solution: We guess T(n) = O(nlgn). Assume T(n) ≤ c nlgn. This must be true for some c > 0 and n = 2. Assuming this relation holds for T(k) when k ≤ (n/2), we have T(n) = 2T(n/2) + n ≤ 2(cn/2 lg (n/2)) + n ≤ 2(cn/2)lg (n/2) + n ≤ cnlg (n/2) + n ≤ cn(lg n -1) + n = cn lgn –cn + n ≤ cn lgn (if c ≥ 1) Therefore, we can select a constant c such that T(n) ≤ cnlgn for all n > 1, which means that T(n) = O(nlgn). Note. We often use variable transformation before solving the relations. Example 9. T(n) = 2T(  ) + lg n.
Setting n = 2k, the above relation becomes T(2k) = 2T(2k/2) + k. Let T(n) = S(k), we obtain S(k) = 2S(k/2) + k = O(klgk). Then, we have T(n) = O(klgk) = O(lg n lglg n). The summation method and recursion-tree method The summation method is demonstrated by the following example. Example 10. Solve T(n) = 2T(n/2) + nlgn. Solution: Setting n = 2k, the above relation becomes T(2k) = 2T(2k-1) + k2k Letting W(k) = T(2k), we have W(k) = 2W(k-1) + k2k = 2[2W(k-2) + (k-1)2k-1] + k2k = 22W(k-2) + (k-1)2k + k2k = 22[2W(k-3) + (k-2)2k-2] + (k-1)2k + k2k = 23W(k-3) + (k-2)2k + (k-1)2k + k2k = …… = 2k-1W(1) + 2×2k + 3×2k + …+ (k-1)2k + k2k = 2k-1W(1) + 2k [2 + 3 + …+ (k-2) + (k-1) + k] = 2k-1W(1) + 2k [k(k+1)/2 -1] = Q(k22k) = Q(nlg2n). The summation steps can be illustrated by a recursion-tree as follows. (d) 
Fig. 1 The construction of recursion tree for W(k) = 2W(k-1) + k2k of Example 10, where (b) and (c) show the first two recursion steps. The Master method The Master method directly gives the answer to the recurrence relation (1) if the function f(n) satisfies certain conditions. Theorem 1 (Master Theorem) Given a recurrence relation T(n) = aT(n/b) + f(n), where a and b are two positive constants, the asymptotic bound of T(n) can be obtained in the following cases: If f(n) = O(  ) for some e > 0,
then T(n) = Q(  ).
If f(n) = Q( ), then T(n) = Q(lgn).
If f(n) = (  ) for some e > 0, and
if af(n/b) ≤ cf(n) for some c < 1 and all n > n0, then T(n) = Q(f(n)). Download 428.46 Kb. Share with your friends:
|