Introduction to Algorithms Second Edition by：算法导论第二版的

1、Chapter 2.Getting StartedOutlineFamiliarize you with the framework to think about the design and analysis of algorithmsIntroduce two sorting algorithms: insertion sort and merge sort Start to understand how to analyze the efficiency of algorithmsWe mainly concern about running time, or speed. Other

2、issues could also affect efficiency, e.g. memory, storage.Example: Sorting ProblemInput: A sequence of n numbersOutput: A permutation (reordering) of the input sequence such that PseudocodeDescribe algorithms as programs written in a pseudo codeEmploy whatever expressive method is most clear and con

3、cise to specify a given algorithmNot concerned with issues of software engineering, such as data abstraction, modularity and error handling Insertion SortIt is an efficient algorithm for sorting a small number of elementsIt works the way many people sort a hand of playing cardsIn insertion sort, the

4、 input numbers are sorted in place: the number are rearranged within the arrayInsertion SortFind an appropriate position to insert the new card into sorted cards in handsComparing and exchange in reverse orderProve the CorrectnessDesign, Prove and AnalyzeOften Use a loop invariantHow to define loop

5、invariant is importantE.g. for insertion sort:Loop invariant: At the start of each iteration of the “outer” for loop (line1-8)- the loop indexed by j - the sub-array A1 . . j-1 consists of the elements originally in A1 . j-1 but in sorted order.Loop InvariantTo use a loop invariant to prove correctn

6、ess, show three things about it:Initialization: It is true prior to the first iteration of the loop.Maintenance: If it is true before an iteration of the loop, it remains true before the next iteration.Termination: When the loop terminates, the invariantusually along with the reason that the loop te

7、rminatedgives us a useful property that helps show that the algorithm is correct.Analyzing algorithmsRandom-access machine(RAM) modelHow do we analyze an algorithms running time?The time taken by an algorithm depends on the input itself (e.g. already sorted)Input size: depends on the problem being s

8、tudied. (parameterize in input size)Want upper bound (guarantee to users)Running time: on a particular input, it is the number of primitive operations(steps) executed.RAM MODEL Do not model the memory hierarchyKinds of Analysis Worst-case (Usually) T(n)=max time on any input of size n Average-case (

9、Sometimes) T(n)=expected time over all input of size n How do we know the probability of every particular input is? I do not know. Make assumption of statistical distribution of inputs (what is the common assumption? ) Best-Case (bogus) Some slow algorithms work well on some input , cheating. Detail

10、ed Analysis of Algorithmn : the number of inputst j : the # of times the while loop test is executed.The loop test is executed one time more than the loop body.Thus, the running time of the above Insertion-Sort algorithm is:T(n) = c1n + c2(n-1) + c4(n-1) + c5 j=2 . n tj+ c6 j=2 . n(tj -1) + c7 j=2 .

11、 n(tj -1) + c8(n-1) = (c5/2 + c6/2 + c7/2) n2 + (c1 + c2 + c4 + c5/2 - c6/2 - c7/2 + c8) n (c2+c4+c5+c8).t j : the # of times the while loop test is executed.The loop test is executed one time more than the loop body.Thus, the running time of the above Insertion-Sort algorithm is:T(n) = c1n + c2(n-1

12、) + c4(n-1) + c5 j=2 . n tj+ c6 j=2 . n(tj -1) + c7 j=2 . n(tj -1) + c8(n-1)Detailed Analysis of Running timeThis worst-case running time can be expressed as an2+bn+c , it is thus a quadratic functionAnalysis of Insertion SortThe running time of the algorithm is: (cost of statement) x ( # of times s

13、tatement is executed) all statementstj = # of times that while loop test is executed for that value of j.Best case: the array is already sorted (all tj = 1)Worst case: the array is in reverse order (tj = j).The worst case running time gives a guaranteed upper bound on the running time for any input.

14、Average case: On average, the key in A j is less than half the elements in A1 . j-1 and its greater than the other half. (tj = j /2).n(n-1)/2Order of Growth The abstraction to ease analysis and focus on the important features. Look only at the leading term of the formula for running time.Drop lower-

15、order terms.Ignore the constant coefficient in the leading term. Example: an + bn + c = (n)Drop lower-order terms anIgnore constant coefficient nThe worst case running time T(n) grows like n; it does not equal n.The running time is (n) to capture the notion that the order of growth is n.Order of gro

16、wth (2)We usually consider one algorithm to be more efficient than another if its worst-case running time has a lower order of growthDue to constant factors and lower-order terms, this evaluation may be error for small inputs but for large enough inputs, it is true.Designing algorithmsDivide and Con

17、querDivide the problem into a number of subproblems.Conquer the subproblems by solving them recursively.Base case: If the subproblems are small enough, just solve them.Combine the subproblem solutions to give a solution to the original problem.Cf.) Incremental method insertion sort.Merge SortA sorti

18、ng algorithm based on divide and conquer. The worst-case running time: Tmerge_sort the size of a subproblem.Use this technique when we analyze recursive algorithmLine 1-3 and 8-11 takes constant time and for loop takes (n1+n2) timeLoop Invariant of MERGELoop Invariant At the start of each iteration

19、of the for loop of lines 12-17, the subarray Apk-1 contains k-p elements of L1.n1+1 and R1. n2+1,in sorted order. Moreover, Li and Rj are the smallest elements of their arrays that have not been copied back into A.Show correctness using loop invariantWe show this loop invariant holds priori to the first iteration of the for loop and each iteration maintains the invariant and the invariant show correctness when the loop terminates.Loop InvariantInitialization Priori to the first iteration of the loop, we have k=p. Ap.k-1 is