📄 page_667.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"> <html> <head> <title>page_667</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_666.html">< previous page</a></td> <td align="center" width="40%" style="background: #EEF3E2"><strong style="color: #2F4F4F; font-size: 120%;">page_667</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_668.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 667</font></td></tr></table><table cellspacing="0" border="0" width="530" cellpadding="4"><tr><td colspan="2" 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"><i>T</i></font><i><font face="Times New Roman, Times, Serif" size="1">EORETICAL FOUNDATIONS</font></i></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table></td></tr><tr><td colspan="2" 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">Complexity of Searching and Sorting</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="2" 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">We introduced Big-O notation in Chapter 6 as a way of comparing the work done by different algorithms. Let's apply it to the algorithms that we've developed in this chapter and see how they compare with each other. In each algorithm, we start with a list containing some number of values. We'll refer to the number of values as <i>N.</i></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="2" 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 the worst case, our original Search function scans all <i>N</i> values to locate an item. Thus, it requires <i>N</i> steps to execute. On average, `Search~ takes roughly <i>N/</i>2 steps to find an item; however, recall that in Big-O notation, we ignore constant factors (as well as lower-order terms). Thus, function `Search~ is an order <i>N</i>-that is, an O(<i>N)</i>-algorithm.</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="2" 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="Courier New, Courier, Mono New, Courier, Mono" size="3">Search2</font><font face="Times New Roman, Times, Serif" size="3"> is also an O(<i>N)</i> algorithm because, even though we saved a comparison on each loop iteration, the same number of iterations are performed. However, making the loop more efficient without changing the number of iterations decreases the constant (the number of steps) that <i>N</i> is multiplied by in the algorithm's work formula. Thus, function </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">Search2</font><font face="Times New Roman, Times, Serif" size="3"> is said to be a constant factor faster than </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">Search</font><font face="Times New Roman, Times, Serif" size="3">.</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="2" 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">What about </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">SearchOrd?</font><font face="Times New Roman, Times, Serif" size="3"> The number of iterations is decreased for the case in which the item is missing from the list. However, all we have done is take a case that would require <i>N</i> steps and reduce its time, on average, to <i>N/</i>2 steps. Thus, </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">SearchOrd</font><font face="Times New Roman, Times, Serif" size="3"> is also O(<i>N).</i></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="2" 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">Now consider </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">BinSearch</font><font face="Times New Roman, Times, Serif" size="3">. In the worst case, it eliminates half of the remaining array components on each iteration. Thus, the worst-case number of iterations is equal to the number of times <i>N</i> must be divided by 2 to eliminate all but one value. This number is computed by taking the logarithm, base 2, of <i>N</i>(written log</font><font face="Times New Roman, Times, Serif" size="1"><sub>2</sub></font><font face="Times New Roman, Times, Serif" size="3"><i>N).</i> Here are some examples of log</font><font face="Times New Roman, Times, Serif" size="1"><sub>2</sub></font><font face="Times New Roman, Times, Serif" size="3"><i>N</i> for different values of <i>N:</i></font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table></td></tr><tr><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><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 align="center"><font face="Times New Roman, Times, Serif" size="3"><i>N</i></font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><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 align="center"><font face="Times New Roman, Times, Serif" size="3"><i>Log</i></font><i><font face="Times New Roman, Times, Serif" size="1"><sub>2</sub></font><font face="Times New Roman, Times, Serif" size="3"> N</font></i></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table></td></tr><tr><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><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 align="right"><font face="Times New Roman, Times, Serif" size="3">2</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><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 align="center"><font face="Times New Roman, Times, Serif" size="3">1</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table></td></tr><tr><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><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 align="right"><font face="Times New Roman, Times, Serif" size="3">4</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><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 align="center"><font face="Times New Roman, Times, Serif" size="3">2</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table></td></tr><tr><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><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 align="right"><font face="Times New Roman, Times, Serif" size="3">8</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table></td><td valign="top"><table border="0" cellspacing="0" cellpadding="0" width="100%"><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 align="center"><font face="Times New Roman, Times, Serif" size="3">3</font></td><td></td></tr><tr><td colspan="3"></td>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -