📄 page_668.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"> <html> <head> <title>page_668</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_667.html">< previous page</a></td> <td align="center" width="40%" style="background: #EEF3E2"><strong style="color: #2F4F4F; font-size: 120%;">page_668</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_669.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 668</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 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">As you can see, for a list of over 1 billion values, </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">BinSearch</font><font face="Times New Roman, Times, Serif" size="3"> takes only 30 iterations. It is definitely the best choice for searching large lists. Algorithms such as </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">BinSearch</font><font face="Times New Roman, Times, Serif" size="3"> are said to be of <i>logarithmic order.</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 let's turn to sorting. Function </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">SelSort</font><font face="Times New Roman, Times, Serif" size="3"> contains nested For loops. The total number of iterations is the product of the iterations performed by the two loops. The outer loop executes <i>N</i>-1 times. The inner loop also starts out executing <i>N</i>-1 times, but steadily decreases until it performs just one iteration: the inner loop executes <i>N</i>/2 iterations. The total number of iterations is thus</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"><img src="bd3ceb9dac4b8424c3add777f26ae133.gif" border="0" alt="0668-01.gif" width="65" height="33" /></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">Ignoring the constant factor and lower-order term, this is <i>N</i></font><font face="Times New Roman, Times, Serif" size="2"><sup>2</sup></font><font face="Times New Roman, Times, Serif" size="3"> iterations, and </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">SelSort</font><font face="Times New Roman, Times, Serif" size="3"> is an O(<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. Consider that, whereas </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">BinSearch</font><font face="Times New Roman, Times, Serif" size="3"> takes only 30 iterations to search an ordered array of 1 billion values, putting the array into order takes </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">SelSort</font><font face="Times New Roman, Times, Serif" size="3"> approximately 1 billion times 1 billion iterations!</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 mentioned that in a case study we would develop the technique of inserting values into an ordered list as they are input. In the meantime, we can consider the approach in the abstract. On average, </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">Insert</font><font face="Times New Roman, Times, Serif" size="3"> has to shift down half of the values (<i>N)/2</i> in the list; thus, it is an O(<i>N)</i> algorithm. If </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">Insert</font><font face="Times New Roman, Times, Serif" size="3"> is called for each input value, we are executing an O(<i>N)</i> algorithm <i>N</i> times; therefore, sorting with insertion is and O(<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.</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">Is every sorting algorithm O(<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"> Most of the simpler ones are, but O(<i>N</i> * 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> sorting algorithms exist. Algorithms that are O(<i>N</i> * 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> are much closer in performance to O(<i>N)</i> algorithms than are O(<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"> algorithms. For example, if <i>N</i> is one million, then an O(<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 takes a million times a million (one trillion) iterations, but an O(<i>N</i> * 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> algorithm takes only 20 million iterations-that is, it is 20 times slower than the O(<i>N)</i> algorithm but 50,000 times faster than the O(<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.</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table></td></tr></table><br /><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 let's turn our attention to a second application of arrays-a special kind of array that is useful when working with alphanumeric data.</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="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">Working with Character Strings</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">In Chapter 2, we introduced string constants. Syntactically, a string constant is a sequence of characters enclosed by double quotes:</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="Courier New, Courier, Mono New, Courier, Mono" size="2">"Hi"</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">A string constant is stored as a </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">char</font><font face="Times New Roman, Times, Serif" size="3"> array with enough components to hold each specified character plus one more-the <i>null character.</i> The null character, which is the first character in both the ASCII and EBCDIC character sets, has internal representation </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">0</font><font face="Times New Roman, Times, Serif" size="3">. In C++, the escape sequence </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">\0</font><font face="Times New Roman, Times, Serif" size="3"> stands for</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_667.html">< previous page</a></td> <td align="center" width="40%" style="background: #EEF3E2"><strong style="color: #2F4F4F; font-size: 120%;">page_668</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_669.html">next page ></a></td> </tr> </table> </body> </html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -