📄 page_285.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"> <html> <head> <title>page_285</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_284.html">< previous page</a></td> <td align="center" width="40%" style="background: #EEF3E2"><strong style="color: #2F4F4F; font-size: 120%;">page_285</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_286.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 285</font></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"><img src="db8e42695999c05940973c7adae4cc57.gif" border="0" alt="0285-01.gif" width="426" height="82" /></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">By itself, the inner loop performs <i>S</i></font><font face="Times New Roman, Times, Serif" size="1"><sub>2</sub></font><font face="Times New Roman, Times, Serif" size="3">* <i>L</i> steps, but because it is repeated <i>N</i> times by the outer loop, it accounts for a total of <i>S</i></font><font face="Times New Roman, Times, Serif" size="1"><sub>2</sub></font><font face="Times New Roman, Times, Serif" size="3">* <i>L</i> * <i>N</i> steps. If <i>L</i> is a constant, then the algorithm still executes in linear 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">Now, suppose that for each of the <i>N</i> outer loop iterations, the inner loop performs <i>N</i> steps (<i>L = N).</i> Here the formula for the total steps is</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">(<i>S</i></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>*<i>N</i>)+(<i>S</i></font><font face="Times New Roman, Times, Serif" size="1"><sub>1</sub></font><font face="Times New Roman, Times, Serif" size="3">*<i>N</i>)+<i>S</i></font><font face="Times New Roman, Times, Serif" size="1"><sub>0</sub></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">or</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">(<i>S</i></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></font><font face="Times New Roman, Times, Serif" size="2"><sup>2</sup></font><font face="Times New Roman, Times, Serif" size="3">)+(<i>S</i></font><font face="Times New Roman, Times, Serif" size="1"><sub>1</sub></font><font face="Times New Roman, Times, Serif" size="3">)+<i>S</i></font><font face="Times New Roman, Times, Serif" size="1"><sub>0</sub></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">Because <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"> grows much faster than <i>N</i> (for large values of <i>N),</i> the inner loop term (<i>S</i></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></font><font face="Times New Roman, Times, Serif" size="2"><sup>2</sup></font><font face="Times New Roman, Times, Serif" size="3">) accounts for the majority of steps executed and the work done. So the corresponding execution time is essentially proportional to <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">. If we have a doubly nested loop, where each loop depends on <i>N,</i> then the expression is</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">(<i>S</i></font><font face="Times New Roman, Times, Serif" size="1"><sub>3</sub></font><font face="Times New Roman, Times, Serif" size="3">*<i>N</i></font><font face="Times New Roman, Times, Serif" size="2"><sup>3</sup></font><font face="Times New Roman, Times, Serif" size="3">)+(<i>S</i></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></font><font face="Times New Roman, Times, Serif" size="2"><sup>2</sup></font><font face="Times New Roman, Times, Serif" size="3">)+(<i>S</i></font><font face="Times New Roman, Times, Serif" size="1"><sub>1</sub></font><font face="Times New Roman, Times, Serif" size="3">*<i>N</i>)+<i>S</i></font><font face="Times New Roman, Times, Serif" size="1"><sub>0</sub></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">and the work and time are proportional to <i>N</i></font><font face="Times New Roman, Times, Serif" size="2"><sup>3</sup></font><font face="Times New Roman, Times, Serif" size="3">whenever <i>N</i> is reasonably large.</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">The table below shows the number of steps required for each increase in the exponent 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"><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>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"><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>N</i></font><i><font face="Times New Roman, Times, Serif" size="2"><sup>0</sup></font><font face="Times New Roman, Times, Serif" size="3"> (Constant)</font></i></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>N</i></font><i><font face="Times New Roman, Times, Serif" size="2"><sup>1</sup></font><font face="Times New Roman, Times, Serif" size="3"> (Linear)</font></i></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>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"> (Quadratic)</font></i></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>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"> (Cubic)</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">1</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><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">1</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="right"><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><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">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">10</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>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -