Đang chuẩn bị liên kết để tải về tài liệu:
Data Structures and Algorithms: Analysis of Algorithms

Data Structures and Algorithms: Analysis of Algorithms includes what to do with algorithms? (Programmer needs to develop a working solution, Client wants problem solved efficiently, Theoretician wants to understand); Why analyze algorithms?. | Analysis of Algorithms Data Structures and Algorithms Acknowledgement: These slides are adapted from slides provided with Data Structures and Algorithms in C++ Goodrich, Tamassia and Mount (Wiley, 2004) Motivation What to do with algorithms? Programmer needs to develop a working solution Client wants problem solved efficiently Theoretician wants to understand Why analyze algorithms? To compare different algorithms for the same task To predict performance in a new environment To set values of algorithm parameters Algorithm Analysis 2 Outline and Reading Running time (§4.2) Pseudo-code Counting primitive operations (§4.2.2) Asymptotic notation (§4.2.3) Asymptotic analysis (§4.2.4) Case study (§4.2.5) Algorithm Analysis 3 Running Time We are interested in the design of "good" data structures and algorithms. Measure of "goodness": Running time (most important) Space usage The running time of an algorithm typically grows with the input size, and is affected by other factors: Hardware environments: processor, memory, disk. Software environments: OS, compiler. Focus: input size vs. running time. Algorithm Analysis 4 Experimental Studies 9000 8000 7000 Time (ms) Write a program implementing the algorithm Run the program with inputs of varying size and composition Use a method like System.currentTimeMillis() or clock() to get an accurate measure of the actual running time Plot the results 6000 5000 4000 3000 2000 1000 0 0 50 100 Input Size Algorithm .