text1-21.htm
来自「浙江大学计算机学院数据结构课程的教学课件」· HTM 代码 · 共 161 行
HTM
161 行
<html>
<head>
<title>Untitled Document</title>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
</head>
<body bgcolor="#FFFFFF" link="#0000FF" vlink="#3399FF" alink="#FF0066">
<div id="Layer1" style="position:absolute; width:711px; height:21px; z-index:1; top: 10px; background-color: #CCCCCC; layer-background-color: #CCCCCC; border: 1px none #000000; left: 26px">
<b>|</b><font face="宋体" size="2">第一章</font><b>|</b><font face="宋体" size="2"><a href="text2-0.htm">第二章</a></font><b>|</b><font face="宋体" size="2"><a href="text3-0.htm">第三章</a></font><b>|</b><font face="宋体" size="2"><a href="text4-0.htm">第四章</a></font><b>|</b><font face="宋体" size="2"><a href="text5-0.htm">第五章</a></font><b>|</b><font face="宋体" size="2"><a href="text6-0.htm">第六章</a></font><b>|</b><font face="宋体" size="2"><a href="text7-0.htm">第七章</a></font><b>|</b><font face="宋体" size="2"><a href="text8-0.htm">第八章</a></font><b>|</b><font face="宋体" size="2"><a href="text9-0.htm">第九章</a></font><b>|</b><font face="宋体" size="2"><a href="text10-0.htm">第十章</a></font><b>|</b><font size="2" face="宋体"><a href="textA-0.htm">算法分析</a><b><font color="#000000">|</font></b>
</font></div>
<div id="Layer1" style="position:absolute; width:724px; height:21px; z-index:1; top: 10px; background-color: #CCCCCC; layer-background-color: #CCCCCC; border: 1px none #000000; left: 26px">
<b>|</b><font face="宋体" size="2">第一章</font><b>|</b><font face="宋体" size="2"><a href="../text2/text2-0.htm">第二章</a></font><b>|</b><font face="宋体" size="2"><a href="../text3/text3-0.htm">第三章</a></font><b>|</b><font face="宋体" size="2"><a href="../text4/text4-0.htm">第四章</a></font><b>|</b><font face="宋体" size="2"><a href="../text5/text5-0.htm">第五章</a></font><b>|</b><font face="宋体" size="2"><a href="../text6/text6-0.htm">第六章</a></font><b>|</b><font face="宋体" size="2"><a href="../text7/text7-0.htm">第七章</a></font><b>|</b><font face="宋体" size="2"><a href="../text8/text8-0.htm">第八章</a></font><b>|</b><font face="宋体" size="2"><a href="../text9/text9-0.htm">第九章</a></font><b>|</b><font face="宋体" size="2"><a href="../text10/text10-0.htm">第十章</a></font><b>|</b><font size="2" face="宋体"><a href="../textA/textA-0.htm">算法分析</a><b><font color="#000000">|</font></b>
</font></div>
<pre><font face="Arial, Helvetica, sans-serif" color="#000000" size="4"><b>
<font size="5" color="#FF0033"> 1.5 Performance measurement</font>
<font color="#FF0066">★<font color="#000000"><i>G</i></font></font><i>enerate a suitable large number of random test data</i>
<font color="#FF3399">★</font><i>Measure average case times</i>
<font color="#3333FF"><i>method1: </i><font color="#FF0033"> use clock to time events</font></font>
clock ( ) ------ the internal processor time
<font size="3">CLK_TCK </font> ------ the number of clock ticks per second
# include <time.h><time.h>
clock_t start, stop (<i>call clock() </i>)
double duration
<font color="#FF0033">duration</font> = ((double) ( stop - star)) / <font size="3">CLK_TCK</font> <second>
<i><font color="#0000FF">method2: </font></i> <font color="#FF0033">use time</font>
# include <time.h><time.h>
time_t start, stop (call time (null) )
double duration
<font color="#FF0033"> duration</font><font color="#FF0066"> </font>= (double) ( difference (stop,star)) <second>
<font color="#0000FF">【example】</font><font color="#FF0033">The worst case performance of the selection
sort function</font>
#include<stdio.h><stdio.h>
#include<time.h> <time.h>
#define <font size="3">MAX_SIZE 1601</font>
#define<font size="3"> INTERACTIONS 26</font> <font color="#ff0099" size="3"> /*26种不同的交换个数*/</font>
#define <font size="3">SWAP(x, y, t ) ((t) = (x), (x) = (y), (y) = (t)))</font>
void main (void)
{
int i, j, position;
int list[MAX_SIZE];
int sizelist[ ] = {<i><font size="3">1,10,20, 30, 40, 50, 60, 70, 80, 90, 100, 200, 300, 400,
500, 600, 700, 800, 900, 1000, 1100, 1200, 1300, 1400,
1500, 1600</font></i>};
clock_t start, stop;
double duration;
printf (" n time\n");
for ( i =0; i < interactions; i++ ) {
for ( j =0; j <sizelist [ i ]; j ++ )
list ] = sizelist - ;
star = clock ( );
sort list, sizelist ]);
stop = clock
/* CLK_TCK = number of clock ticks per second */
duration = ((double start )) / CLK_TCK;
printf"%6d %f \ n", sizelist[ ], duration);
} time
30 … 100 .00 900 1 .86
200 .11 1000 2.31
300 .22 1100 2.80
400 .38 1200 3.35
500 .60 1300 3.90
600 .82 1400 4.54
700 1.15 1500 5.22
800 1.48 1600 5.93
【example】Worst case performance for sequential search function:
int seqsearch (int list[ searchnum, n)
{ an array, that has number, return , if -1, searchnum is not in the i; != searchnum; ++) ((i >< sizelist[i]; j++ )
list [ j ] = sizelist [ i ] - j ; <font size="3" color="#ff0099"> /*worst order*/ </font>
star = clock ( );
sort ( list, sizelist [ i ]);
stop = clock ( );
<font color="#FF0099" size="3"> /* CLK_TCK = number of clock ticks per second */</font>
duration = ((double ) ( stop - start )) / <font size="3">CLK_TCK;</font>
printf ("%6d %f \ n", sizelist[ i ], duration);
}
}
</b></font></pre>
<table width="519" border="1" height="280">
<tr>
<td width="109" height="45">
<div align="center"><font face="Arial, Helvetica, sans-serif" color="#0000FF" size="3"><b>
n</b></font></div>
</td>
<td width="136" height="45">
<div align="center"><font face="Arial, Helvetica, sans-serif" color="#0000FF" size="3"><b>
time </b></font></div>
</td>
<td width="119" height="45">
<div align="center"><font face="Arial, Helvetica, sans-serif" color="#0000FF" size="3"><b>n
</b></font></div>
</td>
<td colspan="2" width="127" height="45">
<div align="center"><font face="Arial, Helvetica, sans-serif" color="#0000FF" size="3"><b>
time</b></font></div>
</td>
</tr>
<tr>
<td height="205" width="109"><font face="Arial, Helvetica, sans-serif" color="#000000" size="3"><b>
30 … 100<br>
200<br>
300<br>
400<br>
500<br>
600<br>
700<br>
800</b></font></td>
<td height="205" width="136"><font face="Arial, Helvetica, sans-serif" color="#000000" size="3"><b>
.00<br>
.11<br>
.22 <br>
.38 <br>
.60<br>
.82 <br>
1.15 <br>
1.48 </b></font></td>
<td height="205" width="119"><font face="Arial, Helvetica, sans-serif" color="#000000" size="3"><b>
900<br>
1000<br>
1100 <br>
1200<br>
1300 <br>
1400<br>
1500 <br>
1600 </b></font></td>
<td colspan="2" height="205" width="127"> <font size="3"> </font><font face="Arial, Helvetica, sans-serif" color="#000000" size="3"><b>1.86</b></font><font size="3"><br>
</font><font face="Arial, Helvetica, sans-serif" color="#000000" size="3"><b>2.31</b></font><font size="3"><br>
</font><font face="Arial, Helvetica, sans-serif" color="#000000" size="3"><b>2.80</b></font><font size="3"><br>
</font><font face="Arial, Helvetica, sans-serif" color="#000000" size="3"><b>3.35</b></font><font size="3"><br>
</font><font face="Arial, Helvetica, sans-serif" color="#000000" size="3"><b>3.90</b></font><font size="3"><br>
<font face="Arial, Helvetica, sans-serif" color="#000000"><b>4.54</b></font><br>
</font><font face="Arial, Helvetica, sans-serif" color="#000000" size="3"><b>5.22</b></font><font size="3"><br>
<font face="Arial, Helvetica, sans-serif" color="#000000"><b>5.93</b></font></font></td>
</tr>
</table>
<pre><font face="Arial, Helvetica, sans-serif" color="#000000" size="4"><b> </b></font><font face="Arial, Helvetica, sans-serif" color="#000000" size="4"><b> <font color="#FF3333">time</font><img src="image/Image16.gif" width="523" height="242"> <font color="#FF3333">n</font>
</b></font></pre>
<table width="731" cellspacing="0" cellpadding="0">
<tr>
<td width="327"> </td>
<td width="271"><a href="../index.htm"><img width="60" height="25" usemap="#MapMap4" border="0" src="../../images/home.gif"></a><a href="../index.htm"><map name="MapMap4"><area shape="rect" coords="42,-34,88,-15" href="text0.htm"><area shape="rect" coords="4,4,55,23" href="text1-index.htm"></map></a></td>
<td width="131"><font face="楷体_GB2312" size="2"><b><a href="text1-20.htm">上一页</a>
<a href="text1-22.htm">下一页</a> </b></font></td>
</tr>
</table>
<pre> </pre>
</body>
</html>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?