next up previous contents index CD CD Algorithms
Next: Expressing Algorithms Up: Correctness and Efficiency Previous: Correctness

Efficiency

The skilled algorithm designer is an efficiency expert. Through cunning and experience we seek to get jobs done as quickly as possible. The benefits of finding an efficient algorithm for a computationally expensive job can be mind-boggling, as illustrated by several of the war stories scattered through this book. Section gif shows how clever algorithms yielded a program that was 30,000 times faster than our initial attempt!

Upon realizing that a given application runs too slowly, the practical person usually asks the boss to buy them a faster machine. Sometimes this is the cheapest option. However, the potential win from faster hardware is typically limited to a factor of ten or so, due to technical constraints (they don't make faster machines) or economic ones (the boss won't pay for it).  

To realize larger performance improvements, we must seek better algorithms. As we will show, a faster algorithm running on a slower computer will always win for sufficiently large instances. Always. Usually, problems don't have to get very large before the faster algorithm wins.

Be aware that there are situations where finding the most efficient algorithm for a job is a complete waste of programmer effort. In any program, there is usually one bottleneck that takes the majority of computing time. The typical claim is that 90% of the run time of any program is spent in 10% of the code. Optimizing the other 90% of the program will have little impact on the total run time. Further, many programs are written with only one or two special instances in mind. If the program will be run just a few times, or if the job can easily be run overnight, it probably does not pay to make the programmer work harder in order to reduce cycle consumption.  


next up previous contents index CD CD Algorithms
Next: Expressing Algorithms Up: Correctness and Efficiency Previous: Correctness

Algorithms
Mon Jun 2 23:33:50 EDT 1997