Analysis ofAlgorithms Department of Computer Science 算法分析计算机科学系.pptVIP

Analysis of Algorithms Analysis of Algorithms Running Time Pseudo-Code Analysis of Algorithms Asymptotic Notation Asymptotic Analysis Mathematical facts Average Case vs. Worst Case Running Timeof an algorithm An algorithm may run faster on certain data sets than on others. Finding the average case can be very difficult, so typically algorithms are measured by the worst-case time complexity. Also, in certain application domains (e.g., air traffic control, surgery, IP lookup) knowing the worst-case time complexity is of crucial importance. Measuring the Running Time How should we measure the running time of an algorithm? Approach 1: Experimental Study Write a program that implements the algorithm Run the program with data sets of varying size and composition. Use a method like System.currentTimeMillis() to get an accurate measure of the actual running time. Beyond Experimental Studies Experimental studies have several limitations: It is necessary to implement and test the algorithm in order to determine its running time. Experiments can be done only on a limited set of inputs, and may not be indicative of the running time on other inputs not included in the experiment. In order to compare two algorithms, the same hardware and software environments should be used. Beyond Experimental Studies We will now develop a general methodology for analyzing the running time of algorithms. In contrast to the experimental approach, this methodology: Uses a high-level description of the algorithm instead of testing one of its implementations. Takes into account all possible inputs. Allows one to evaluate the efficiency of any algorithm in a way that is independent from the hardware and software environment. Pseudo-Code Pseudo-code is a description of an algorithm that is more structured than usual prose but less formal than a programming language. Example: finding the maximum element of an array. Algorithm arrayMax(A, n): Input: An array A storing n integers. Output: The max