Java Reference
In-Depth Information
3
Algorithm Analysis
How long will it take to process the company payroll once we complete our planned
merger? Should I buy a new payroll program from vendor X or vendor Y? If a
particular program is slow, is it badly implemented or is it solving a hard problem?
Questions like these ask us to consider the difficulty of a problem, or the relative
efficiency of two or more approaches to solving a problem.
This chapter introduces the motivation, basic notation, and fundamental tech-
niques of algorithm analysis. We focus on a methodology known as asymptotic
algorithm analysis, or simply asymptotic analysis. Asymptotic analysis attempts
to estimate the resource consumption of an algorithm. It allows us to compare the
relative costs of two or more algorithms for solving the same problem. Asymptotic
analysis also gives algorithm designers a tool for estimating whether a proposed
solution is likely to meet the resource constraints for a problem before they imple-
ment an actual program. After reading this chapter, you should understand
• the concept of a growth rate, the rate at which the cost of an algorithm grows
as the size of its input grows;
• the concept of upper and lower bounds for a growth rate, and how to estimate
these bounds for a simple program, algorithm, or problem; and
• the difference between the cost of an algorithm (or program) and the cost of
a problem.
The chapter concludes with a brief discussion of the practical difficulties encoun-
tered when empirically measuring the cost of a program, and some principles for
code tuning to improve program efficiency.
3.1
Introduction
How do you compare two algorithms for solving some problem in terms of effi-
ciency? We could implement both algorithms as computer programs and then run
53
 
Search WWH ::




Custom Search