tailieunhanh - Lecture note Data visualization - Chapter 18

This chapter presents the following content: Running time of function, running time of cubic function, running time of quadratic function, running time of linear function, running time of logarithmic function, logarithm, static searching problem, . | Lecture note Data visualization - Chapter 18 Lecture 18 Recap Running Time of Function Running Time of Cubic Function Running Time of Quadratic Function Running Time of Linear Function Running Time of Logarithmic Function Logarithm Bits in Binary Numbers Repeated Doubling Repeated Halving Checking an Algorithm Analysis Once we have performed an algorithm analysis we want to determine whether it is correct and as good we can possibly make it One way to do so is to code the program and see if the empirically observed running time matches the running time predicted by the analysis Continued . When N increases by a factor of 10 the running time goes up by a factor of 10 for linear programs 100 for quadratic programs and 1000 for cubic programs Programs that run in O N log N take slightly more than 10 times as long to run under the same circumstances These increases can be hard to spot if the lower order terms have relatively large coefficients and N is not large enough An example is the jump from N 10 to N 100 in the running time for the various implementations of the maximum contiguous subsequence sum problem Continued . Another commonly used trick to verify that some program is O F N is to compute the values T N F N for a range of N where T N is the empirically observed running time If F N is a tight answer for the running time the computed values converge to a positive constant If F N is an overestimate the values converge to zero If F N is an underestimate and hence wrong the values diverge Example Empirical running time for N binary searches in an N item array Continued . Note in particular that we do not have definitive convergence One problem is that the clock that we used to time the program ticks only every 10 ms Note also that there is no great difference between O N and O N log N Certainly an O N log N algorithm is much closer to being linear than being quadratic Finally note that the machine in this example has enough memory to store 640 000 objects .