Mastering Algorithms With C - Kyle Loudon [21]
Related Topics
Compiler design
The basics behind the code translators that ultimately dictate how efficiently programs will run, at least at the instruction level. Whereas generally in algorithm design we focus on complexity as a measure of performance (see Chapter 4), understanding the issues compilers deal with in translating code can help us tune performance in practice. Understanding tail recursion is a good example.
Tail recursion elimination
A process in which the final tail-recursive call in a function is replaced with an iterative control structure. This does not change the outcome of the function, but helps avoid the overhead of an extra function call. Tail recursion elimination is a fundamental principle studied in compiler design.
Recursion trees
Illustrations that help us visualize calling sequences with recursive functions. Recursion trees vary in their formality. Figures Figure 3.1 and Figure 3.4 for recursively computing a factorial and Figure 3.6 for determining the prime factors of a number are recursion trees. Recursion trees are most often used with functions containing two or more recursive calls within each activation.
Chapter 4. Analysis of Algorithms
Whether we are designing an algorithm or applying one that is widely accepted, it is important to understand how the algorithm will perform. There are a number of ways we can look at an algorithm's performance, but usually the aspect of most interest is how fast the algorithm will run. In some cases, if an algorithm uses significant storage, we may be interested in its space requirement as well. Whatever the case, determining how an algorithm performs requires a formal and deterministic method.
There are many reasons to understand the performance of an algorithm. For example, we often have a choice of several algorithms when solving problems. Understanding how each performs helps us differentiate between them. Understanding the burden an algorithm places on an application also helps us plan how to use the algorithm more effectively. For instance, garbage collection algorithms, algorithms that collect dynamically allocated storage to return to the heap (see Chapter 3), require considerable time to run. Knowing this, we can be careful to run them only at opportune moments, just as LISP and Java do, for example.
This chapter covers:
Worst-case analysis
The metric by which most algorithms are compared. Other cases we might consider are the average case and best case. However, worst-case analysis usually offers several advantages.
O-notation
The most common notation used to formally express an algorithm's performance. O -notation is used to express the upper bound of a function within a constant factor.
Computational complexity
The growth rate of the resources (usually time) an algorithm requires with respect to the size of the data it processes. O -notation is a formal expression of an algorithm's complexity.
Worst-Case Analysis
Most algorithms do not perform the same in all cases; normally an algorithm's performance varies with the data passed to it. Typically, three cases are recognized: the best case, worst case, and average case. For any algorithm, understanding what constitutes each of these cases is an important part of analysis because performance can vary significantly between them. Consider even a simple algorithm such as linear search. Linear search is a natural but inefficient search technique in which we look for an element simply by traversing a set from one end to the other. In the best case, the element we are looking for is the first element we inspect, so we end up traversing only a single element. In the worst case, however, the desired element is the last one we inspect, in which case we end up traversing all of the elements. On average, we can expect to find the element somewhere in the middle.
Reasons for Worst-Case Analysis
A basic understanding of how