|
|
|
|
|
|
|
(text box continued from previous page) |
|
|
|
|
|
|
|
|
|
loop dominates the total time, we classify an algorithm according to the highest order of N that appears in its work expression, called the order of magnitude, or simply the order of that expression. So we talk about algorithms being order N squared (or cubed or so on) or we describe them with what is called Big-0 notation. We express this order by putting the highest-order term in parentheses with a capital 0 in front. For example, 0(1) is constant time; 0(N) is linear time; 0(N2) is quadratic time; and 0(N3) is cubic time. |
|
|
|
| |
|
|
|
|
Determining the orders of different algorithms allows us to compare the work they require without having to program and execute them. For example, if you had an 0(N2) algorithm and a linear algorithm that performed the same task, you probably would choose the linear algorithm. We say probably because an 0(N2) algorithm actually may execute fewer steps than an 0(N) algorithm for small values of N. Remember that if N is small, the constants and lower-order terms in the work expression may be significant. |
|
|
|
| |
|
|
|
|
Although we generally ignore the lower-order terms, they do exist, giving us a polynomial expression when all the terms are written out. Thus, such algorithms are said to execute in polynomial time and form a broad class of algorithms that encompasses everything we've discussed so far. |
|
|
|
| |
|
|
|
|
In addition to polynomial-time algorithms, we encounter a logarithmic-time algorithm in Chapter 12. There are also factorial (0(N!)), exponential (0(NN)), and hyperexponential (0(NNN)) class algorithms, which can require vast amounts of time to execute and are beyond the scope of this course. For now, the important point to remember is that the looping control structure allows an algorithm to perform more work than the physical number of statements it contains. |
|
|
|
|
|
|
|
|
|
|
Problem-Solving Case Study Average Income by Gender |
|
|
|
|
|
|
|
|
Problem: You've been hired by a law firm that is working on a sex discrimination case. Your firm has obtained a file of incomes, incFile, which contains the salaries for every employee in the company. Each salary amount is preceded by F for female or M for male. As a first pass in the analysis of these data, you've been asked to compute the average income for females and the average income for males. |
|
|
|
|
|
|
|
|
Input: A file, incFile, of floating point salary amounts, with one amount per line. Each amount is preceded by a character (F for female, M for male). This code is the first character on each input line and is followed by a blank, which separates the code from the amount. |
|
|
|
|
|
