📄 page_284.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"> <html> <head> <title>page_284</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_283.html">< previous page</a></td> <td align="center" width="40%" style="background: #EEF3E2"><strong style="color: #2F4F4F; font-size: 120%;">page_284</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_285.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 284</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 continues on next 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">steps. We define a step as any operation roughly equivalent in complexity to a comparison, an I/O operation, or an assignment.</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">Given an algorithm with just a sequence of statements (no branches or loops), the number of steps performed is directly related to the number of statements. When we introduce branches, however, we make it possible to skip some statements in the algorithm. Branches allow us to subtract steps without physically removing them from the algorithm because only one branch is executed at a time. But because we always want to express work in terms of the worst-case scenario, we use the number of steps in the longest branch.</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 consider the effect of a loop. If a loop repeats a sequence of 15 simple statements 10 times, it performs 150 steps. Loops allow us to multiply the work done in an algorithm without physically adding statements.</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 that we have a measure for the work done in an algorithm, we can compare algorithms. For example, if Algorithm A always executes 3124 steps and Algorithm B always does the same task in 1321 steps, then we can say that Algorithm B is more efficientthat is, it takes fewer steps to accomplish the same task.</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">If an algorithm always takes the same number of steps regardless of how many data values it processes, we say that it executes in <i>constant time.</i> Be careful: Constant time doesn't mean small; it means that the amount of work done does not depend on the number of data values.</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">If a loop executes a fixed number of times, the work done is greater than the physical number of statements but is still constant. But what happens if the number of loop iterations can change from one run to the next? Suppose a data file contains <i>N</i> data values to be processed in a loop. If the loop reads and processes one value during each iteration, then the loop executes<i>N</i> iterations. The amount of work done thus depends on a variable, the number of data values. Algorithms that perform work directly proportional to the number of data values are said to execute in <i>linear time.</i> If we have a loop that executes <i>N</i> times, the number of steps to be executed is linearly dependent on <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="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">Specifically, the work done by an algorithm with a data-dependent loop 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"><img src="53737a90b54e2792253ef549ea38815b.gif" border="0" alt="0284-01.gif" width="183" height="120" /></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">where <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"> is the number of steps in the loop body (a constant for a given loop), <i>N</i> is the number of iterations (a variable), and <i>S</i></font><font face="Times New Roman, Times, Serif" size="1"><sub>0</sub></font><font face="Times New Roman, Times, Serif" size="3"> is the number of steps outside the loop. (We can use this same formula for constant-time loops, but <i>N</i> would be a constant.) Notice that if <i>N</i> grows very large, the term <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> dominates the execution time. That is, <i>S</i></font><font face="Times New Roman, Times, Serif" size="1"><sub>0</sub></font><font face="Times New Roman, Times, Serif" size="3"> becomes an insignificant part of the total execution 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">What about a data-dependent loop that contains a nested loop? The number of steps in the inner loop, <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">, and the number of iterations performed by the inner loop, <i>L,</i> must be multiplied by the number of iterations in the outer loop:</font></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 /></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_283.html">< previous page</a></td> <td align="center" width="40%" style="background: #EEF3E2"><strong style="color: #2F4F4F; font-size: 120%;">page_284</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_285.html">next page ></a></td> </tr> </table> </body> </html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -