📄 page_286.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"> <html> <head> <title>page_286</title> <link rel="stylesheet" href="reset.css" type="text/css" media="all"> <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /> </head> <body> <table summary="top nav" border="0" width="100%"> <tr> <td align="left" width="30%" style="background: #EEF3E2"><a style="color: blue; font-size: 120%; font-weight: bold; text-decoration: none; font-family: verdana;" href="page_285.html">< previous page</a></td> <td align="center" width="40%" style="background: #EEF3E2"><strong style="color: #2F4F4F; font-size: 120%;">page_286</strong></td> <td align="right" width="30%" style="background: #EEF3E2"><a style="color: blue; font-size: 120%; font-weight: bold; text-decoration: none; font-family: verdana;" href="page_287.html">next page ></a></td> </tr> <tr> <td align="left" colspan="3" style="background: #ffffff; padding: 20px;"> <table border="0" width="100%" cellpadding="0"><tr><td align="center"> <table border="0" cellpadding="2" cellspacing="0" width="100%"><tr><td align="left"></td> <td align="right"></td> </tr></table></td></tr><tr><td align="left"><p></p><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="right"><font face="Times New Roman, Times, Serif" size="2" color="#FF0000">Page 286</font></td></tr></table><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"></td> <td colspan="3" height="12"></td> <td rowspan="5"></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td><font face="Times New Roman, Times, Serif" size="3"><i>(text box continued from previous page)</i></font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table><table cellpadding="0" cellspacing="0" border="0" width="100%"><tr><td height="12"></td></tr><tr><td><table cellspacing="0" border="0" width="518" cellpadding="7"><tr><td colspan="5" valign="top"><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"></td> <td colspan="3" height="12"></td> <td rowspan="5"></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td><font face="Times New Roman, Times, Serif" size="3">loop dominates the total time, we classify an algorithm according to the highest order of <i>N</i> that appears in its work expression, called the <i>order of magnitude,</i> or simply the <i>order</i> of that expression. So we talk about algorithms being order <i>N</i> 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(<i>N)</i> is linear time; 0(<i>N</i></font><i><font face="Times New Roman, Times, Serif" size="2"><sup>2</sup></font><font face="Times New Roman, Times, Serif" size="3">)</font></i><font face="Times New Roman, Times, Serif" size="3"> is quadratic time; and 0(<i>N</i></font><i><font face="Times New Roman, Times, Serif" size="2"><sup>3</sup></font><font face="Times New Roman, Times, Serif" size="3">)</font></i><font face="Times New Roman, Times, Serif" size="3"> is cubic time.</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table></td></tr><tr><td colspan="5" valign="top"><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"></td> <td colspan="3" height="12"></td> <td rowspan="5"></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td><font face="Times New Roman, Times, Serif" size="3">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(<i>N</i></font><i><font face="Times New Roman, Times, Serif" size="2"><sup>2</sup></font><font face="Times New Roman, Times, Serif" size="3">)</font></i><font face="Times New Roman, Times, Serif" size="3"> algorithm and a linear algorithm that performed the same task, you probably would choose the linear algorithm. We say <i>probably</i> because an 0(<i>N</i></font><i><font face="Times New Roman, Times, Serif" size="2"><sup>2</sup></font><font face="Times New Roman, Times, Serif" size="3">)</font></i><font face="Times New Roman, Times, Serif" size="3"> algorithm actually may execute fewer steps than an 0(<i>N)</i> algorithm for small values of <i>N.</i> Remember that if <i>N</i> is small, the constants and lower-order terms in the work expression may be significant.</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table></td></tr><tr><td colspan="5" valign="top"><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"></td> <td colspan="3" height="12"></td> <td rowspan="5"></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td><font face="Times New Roman, Times, Serif" size="3">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 <i>polynomial time</i> and form a broad class of algorithms that encompasses everything we've discussed so far.</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table></td></tr><tr><td colspan="5" valign="top"><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"></td> <td colspan="3" height="12"></td> <td rowspan="5"></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td><font face="Times New Roman, Times, Serif" size="3">In addition to polynomial-time algorithms, we encounter a logarithmic-time algorithm in Chapter 12. There are also factorial (0(<i>N!)),</i> exponential (0(<i>N</i></font><i><font face="Times New Roman, Times, Serif" size="2"><sup>N</sup></font><font face="Times New Roman, Times, Serif" size="3">)),</font></i><font face="Times New Roman, Times, Serif" size="3"> and hyperexponential (0(<i>N</i></font><i><font face="Times New Roman, Times, Serif" size="2"><sup>NN</sup></font><font face="Times New Roman, Times, Serif" size="3">)) 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.</font></i></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table></td></tr></table></td></tr></table><br /><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"></td> <td colspan="3" height="17"></td> <td rowspan="5"></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td><font face="Times New Roman, Times, Serif" size="3">Problem-Solving Case Study Average Income by Gender</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"></td> <td colspan="3" height="12"></td> <td rowspan="5"></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td><font face="Times New Roman, Times, Serif" size="3"><img src="19f6534fbe3ce048325ac05c45698220.gif" border="0" alt="0286-01.gif" width="129" height="199" /></font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"></td> <td colspan="3" height="12"></td> <td rowspan="5"></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td><font face="Times New Roman, Times, Serif" size="3">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, </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">incFile</font><font face="Times New Roman, Times, Serif" size="3">, 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.</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"></td> <td colspan="3" height="12"></td> <td rowspan="5"></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td><font face="Times New Roman, Times, Serif" size="3">Input: A file, </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">incFile</font><font face="Times New Roman, Times, Serif" size="3">, 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.</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table></td></tr></table><p><font size="0"></font></p>聽 </td> </tr> <tr> <td align="left" width="30%" style="background: #EEF3E2"><a style="color: blue; font-size: 120%; font-weight: bold; text-decoration: none; font-family: verdana;" href="page_285.html">< previous page</a></td> <td align="center" width="40%" style="background: #EEF3E2"><strong style="color: #2F4F4F; font-size: 120%;">page_286</strong></td> <td align="right" width="30%" style="background: #EEF3E2"><a style="color: blue; font-size: 120%; font-weight: bold; text-decoration: none; font-family: verdana;" href="page_287.html">next page ></a></td> </tr> </table> </body> </html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -