文档介绍：Principles of Algorithm Analysis
• Key to good understanding of algorithms for practical applications
– We do not analyze every program we write
– Enough to understand basic [standard] algorithms and their performance so that we can select the best algorithm
for the job at hand
• Important for the study of algorithm properties so that we can save time and resources, with reasonable sacrifice in
terms plexity of coding
Implementation and Empirical Analysis
• Design, develop, and express algorithms in terms of layers of abstract operations
• Empirical analysis
– Compare the performance of two algorithms by actually running them
– Requires a correct plete implementation
– Look for resource usage and time required, with the same input data and running on the same machine, with
the same type of environment
∗ Selection of input data is extremely important
∗ You can select random data, actual data, or perverse data
– Code may execute at different speed depending on load on the system (overall resource usage)
– Useful to validate the mathematical analysis
• Pitfalls in algorithm selection
– Ignoring performance characteristics
∗ Addition of a few lines of code (increase plexity) can endow the code with more intelligence to make
it run faster
– Paying too much attention to performance characteristics
∗ Is it worth spending 10 hours of your time to save 10 milliseconds of run time?
Analysis of algorithms
• It may not be always possible to perform empirical analysis
• Mathematical analysis is more informative and less expensive but can be difficult if we do not know all the mathe-
matical formulas
• The high-level program code may not correctly reflect the performance in terms of machine language
– The code pile differently depending on the level of optimization turned on in piler
• Identify the abstract operations on which the algorithm is based, and separate analysis from implementation (think
of the abstract operations o