📄 texta-3.htm
字号:
<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"><a href="../text1/text1-0.htm">第一章</a></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="宋体">算法分析<b><font color="#000000">|</font></b>
</font></div>
<pre align="left">
<b><font face="Arial, Helvetica, sans-serif" size="4" color="#FF0000">例1.2 找第k个最小元素。</font><font face="Arial, Helvetica, sans-serif" size="4" color="#000000">
一般先分类为递减序列，得到第k个最小元素，要O (nlogn).
分治法可以O (n)内得到第k个最小元素。当k=[n/2]时，成为在线
性时间内找一个序列的中值问题。
<font color="#FF0000"> procedure</font> SELECT(k,s)
<i><font size="3" color="#CC0099"> bagin.</font></i>
<font color="#0033CC">1. </font> if |s|<50 then
<font color="#0033CC">2. </font> <i><font size="3" color="#CC0099">begin </font></i>
<font color="#0033CC">3. </font> 把S分类
<font color="#0033CC">4. </font> return S的第K个最小元素.
<i><font size="3" color="#CC0099"> end</font></i>
<font color="#0033CC">5. </font> <i><font size="3" color="#CC0099"> else </font></i>
<font color="#0033CC">6. </font> <i><font size="3" color="#CC0099"> begin </font></i>
<font color="#0033CC">7. </font> 把S划分成各为五个元素的[|s|/5]个子序列；
<font color="#0033CC">8. </font> 设L是剩余元素（如果有的话）；
<font color="#0033CC">9. </font> 把上述各个5元素序列分类；
<font color="#0033CC">10. </font> 设M是5个元素的中值序列；
<font color="#0033CC">11. </font> m ← SELECT( <img src="image/haf%5B.gif" width="9" height="25" align="middle">|M|/2 <img src="image/haf%5D.gif" width="9" height="25" align="middle">, M)；
<font color="#0033CC">12. </font> 设S1，S2，S3为S的分别<，=，> m的元素序列；
<font color="#0033CC">13. </font> <i><font size="3" color="#CC0099"> if </font></i>|S1|≥k
<i><font size="3" color="#CC0099"> then </font></i> return SELECT(k, S1 )
<i><font size="3" color="#CC0099"> else</font></i>
<font color="#0033CC">14.</font> <i><font size="3" color="#CC0099"> if </font></i> (|S1|+|S2|≥k)
then return m
<font color="#0033CC">15. </font> <i><font size="3" color="#CC0099"> else </font></i>
<font color="#0033CC">16.</font> return SELECT(k-|S1|-|S2|, S3 )
<i><font size="3" color="#CC0099">end
end</font></i>
<img src="image/text10-a.gif" width="517" height="185">
<font color="#FF0000" face="宋体">说明：</font><font face="宋体">
1.把S大问题化为S1，S2，S3 三个小问题。
2.选合适中值，原n变为[n/5]个数中选，速度就快5倍。
至少有1/4的元素</font></font><font face="宋体" size="4" color="#000000"> ≤</font><font face="Arial, Helvetica, sans-serif" size="4" color="#000000"><font face="宋体"> m, 至少有1/4的元素 </font>≥<font face="宋体"> m 。
3.子序列用5分割是算法中有二个SELECT递归调用，每
次是对r|s|的序列调用，
二个序列之和必须<|s|的保证
</font></font></b></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="textA-index.htm"></map></a></td>
<td width="131"><font face="楷体_GB2312" size="2"><b> <a href="texta-2.htm">上一页</a>
<a href="textA-4.htm">下一页</a> </b></font></td>
</tr>
</table>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -