计算机算法导论-第3章.ppt

Introduction to Algorithms 计算机算法导论,20072008年第一学期,Quiz(10 minutes),Question Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in 8n2 steps, while merge sort runs in 64nlgn steps. For which values of n does insertion sort beat merge sort? (n44) What is the smallest value of n such that an algorithm whose running time is 100n2 runs faster than an algorithm whose running time is 2n on the same machine? (n=15),Quiz(10 minutes),Question Use mathematical induction to show that when n is an exact power of 2, the solution of the recurrence is T(n) = nlgn. What is the worst-case running time of an algorithm? Why the worst-case running time is concentrated on?,3、Growth of Functions,Introducing several standard methods for simplifying the asymptotic analysis of algorithms. Defining several types of asymptotic notation Reviewing the behavior of functions in the analysis of algorithms,3.1、Asymptotic notation,Alphabet, (theta) (omicron, “big-oh/little-oh”) (omega, “big-omega/little-omega”),-notation,-notation,-notation,-notation,-notation,-notation,-notation,Asymptotic notation in equations,Asymptotic notation in equations,Asymptotic notation in equations,-notation,-notation,Comparison of functions,Comparison of functions,Comparison of functions,3.2 Standard notations and common functions,Standard notations and common functions,Standard notations and common functions,Standard notations and common functions,Logarithms,Standard no