text1-15.htm

来自「浙江大学计算机学院数据结构课程的教学课件」· HTM 代码 · 共 84 行 · 第 1/2 页

《2》<img src="image/wR.gif" width="26" height="25">
【<font color="#0000FF">definition</font>】f(n) = <img src="image/wB.gif" width="14" height="15">(g(n)) iff there exist positive constants c 
 and n0 such that f(n) >= cg(n) for all n, n>=n0

 3n + 2 = <img src="image/wB.gif" width="14" height="15">(n)               　　3n + 2 >= 3n             　<i>for n >=1  c = 3 , n0=1</i>
10</b></font><font face="Arial, Helvetica, sans-serif" size="4"><b><font face="Arial, Helvetica, sans-serif" size="4"><b><font face="Arial, Helvetica, sans-serif" color="#000000" size="4"><b><font size="3"><img src="image/Image6.gif" width="26" height="21"></font></b></font></b></font></b></font><font face="Arial, Helvetica, sans-serif" color="#000000" size="4"><b>  +4n + 2=<img src="image/wB.gif" width="14" height="15">(</b></font><font face="Arial, Helvetica, sans-serif" size="4"><b><font face="Arial, Helvetica, sans-serif" color="#000000" size="4"><b><font size="3"><img src="image/Image6.gif" width="26" height="21"></font></b></font></b></font><font face="Arial, Helvetica, sans-serif" color="#000000" size="4"><b> )　　１０</b></font><font face="Arial, Helvetica, sans-serif" size="4"><b><font face="Arial, Helvetica, sans-serif" color="#000000" size="4"><b><font size="3"><img src="image/Image6.gif" width="26" height="21"></font></b></font></b></font><font face="Arial, Helvetica, sans-serif" color="#000000" size="4"><b>+4n + 2 >=</b></font><font face="Arial, Helvetica, sans-serif" size="4"><b><font face="Arial, Helvetica, sans-serif" color="#000000" size="4"><b><font size="3"><img src="image/Image6.gif" width="26" height="21"></font></b></font></b></font><font face="Arial, Helvetica, sans-serif" color="#000000" size="4"><b>  <i>     for n >=1  c = 1, n0=1</i> 
6*<font size="3"><img src="image/Image8.gif" width="20" height="26"></font> +</b></font><font face="Arial, Helvetica, sans-serif" size="4"><b><font face="Arial, Helvetica, sans-serif" color="#000000" size="4"><b><font size="3"><img src="image/Image6.gif" width="26" height="21"></font></b></font></b></font><font face="Arial, Helvetica, sans-serif" color="#000000" size="4"><b> = <img src="image/wB.gif" width="14" height="15">(<font size="3"><img src="image/Image8.gif" width="20" height="26"></font> )             　　 6 <font size="3"><img src="image/Image8.gif" width="20" height="26"></font>+</b></font><font face="Arial, Helvetica, sans-serif" size="4"><b><font face="Arial, Helvetica, sans-serif" color="#000000" size="4"><b><font size="3"><img src="image/Image6.gif" width="26" height="21"></font></b></font></b></font><font face="Arial, Helvetica, sans-serif" color="#000000" size="4"><b> <=  <font size="3"><img src="image/Image8.gif" width="20" height="26"></font>         <i>    for n >=1  c =1  , n0=1</i> 
3n + 3= <img src="image/wB.gif" width="14" height="15">(1)                                  
10</b></font><font face="Arial, Helvetica, sans-serif" size="4"><b><font face="Arial, Helvetica, sans-serif" color="#000000" size="4"><b><font size="3"><img src="image/Image6.gif" width="26" height="21"></font></b></font></b></font><font face="Arial, Helvetica, sans-serif" color="#000000" size="4"><b>   +4n +2 = <img src="image/wB.gif" width="14" height="15">(n)   
10 </b></font><font face="Arial, Helvetica, sans-serif" size="4"><b><font face="Arial, Helvetica, sans-serif" color="#000000" size="4"><b><font size="3"><img src="image/Image6.gif" width="26" height="21"></font></b></font></b></font><font face="Arial, Helvetica, sans-serif" color="#000000" size="4"><b>  +4n +2 = <img src="image/wB.gif" width="14" height="15">(1)   
6*<font size="3"><img src="image/Image8.gif" width="20" height="26"></font> +</b></font><font face="Arial, Helvetica, sans-serif" size="4"><b><font face="Arial, Helvetica, sans-serif" color="#000000" size="4"><b><font size="3"><img src="image/Image6.gif" width="26" height="21"></font></b></font></b></font><font face="Arial, Helvetica, sans-serif" color="#000000" size="4"><b> =<img src="image/wB.gif" width="14" height="15"></b></font><font face="Arial, Helvetica, sans-serif" color="#000000" size="4"><b>(</b></font><font face="Arial, Helvetica, sans-serif" size="4"><b><font face="Arial, Helvetica, sans-serif" color="#000000" size="4"><b><font size="3"><img src="image/Image6.gif" width="26" height="21"></font></b></font></b></font><font face="Arial, Helvetica, sans-serif" color="#000000" size="4"><b> )

<font color="#FF0033">f (n)</font> --->  several function <font color="#FF0033">g(n)</font>

<font color="#FF0033">g(n)</font> ---  as large of function of n as possible for which the statement<br>               f(n)=<img src="image/wB.gif" width="17" height="17">(<font size="2">g(n)</font>) is true
　　　
【<font color="#0000FF">Theorem1.3</font>】  If  f(n) = am<img src="image/Image12.gif" width="30" height="21">  + ……+a1n +a0   
     then f(n)=<img src="image/wB.gif" width="14" height="15">( <img src="image/Image12.gif" width="30" height="21">)

《3》 <img src="image/oR.gif" width="19" height="23">
【<font color="#0000FF">definition</font>】f(n) =  <img src="image/ob.gif" width="17" height="17">(g(n)) iff there exist positive constants c1, c2
 and n0 such that  c1 g(n) <= f(n) <= c2 g(n) 　for all n, n>=n0
<br> 3n + 2 = <img src="image/ob.gif" width="17" height="17">(n)         　　 3n <=  3n + 2 <= 4n       c1 =3,  c2 =4   , n0=2
10</b></font><font face="Arial, Helvetica, sans-serif" size="4"><b><font face="Arial, Helvetica, sans-serif" color="#000000" size="4"><b><font size="3"><img src="image/Image6.gif" width="26" height="21"></font></b></font></b></font><font face="Arial, Helvetica, sans-serif" color="#000000" size="4"><b>  +4n + 2= <img src="image/ob.gif" width="17" height="17">(</b></font><font face="Arial, Helvetica, sans-serif" size="4"><b><font face="Arial, Helvetica, sans-serif" color="#000000" size="4"><b><font size="3"><img src="image/Image6.gif" width="26" height="21"></font></b></font></b></font><font face="Arial, Helvetica, sans-serif" color="#000000" size="4"><b> )    
6*<font size="3"><img src="image/Image8.gif" width="20" height="26"></font> +</b></font><font face="Arial, Helvetica, sans-serif" size="4"><b><font face="Arial, Helvetica, sans-serif" color="#000000" size="4"><b><font size="3"><img src="image/Image6.gif" width="26" height="21"></font></b></font></b></font><font face="Arial, Helvetica, sans-serif" color="#000000" size="4"><b> = <img src="image/ob.gif" width="17" height="17">(<font size="3"><img src="image/Image8.gif" width="20" height="26"></font> ) <br>             
【<font color="#0000FF">Theorem1.4</font>】  If  f(n) = am <img src="image/Image12.gif" width="30" height="21"> + ……+a1n +a0  
                                then f(n)=<img src="image/ob.gif" width="17" height="17">( <img src="image/Image12.gif" width="30" height="21">)
  

</b></font></pre>
<table width="731" cellspacing="0" cellpadding="0">
  <tr> 
    <td width="327">&nbsp;</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-14.htm">上一页</a> 
      <a href="text1-16.htm">下一页</a></b></font></td>
  </tr>
</table>
</body>
</html>