📄 text9-26.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">第九章</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 align="left">
<b><font face="Arial, Helvetica, sans-serif" size="4" color="#000000">(4)<font color="#FF0000"> Analysis</font>
〖<font color="#FF0000">Lemma9.3</font>〗 Let a be an F-heap with n elements that results from
a sequence of insert, combine, delete min, delete, and decrease key
operations performed on initially empty F-heap
(a) Let b be any node node in any of the min-trees of a.
The degree of b is at most <img src="image/logqm.gif" width="69" height="28" align="middle"> , where
f = ( 1+ <img src="image/sq5.gif" width="29" height="27" align="middle"> ) / 2 and m is the number of elements in the
subtree with root b.
(b) MAX_DEGREE <= [ <img src="image/logqm.gif" width="69" height="28" align="middle"> ] and the actual cost of a delete
min is O(log n + s)
〖<font color="#FF0000">Theorem9.2</font>〗 If a sequence of n insert, combine, delete min,
delete, and decrease keyoperations is performed on an initially
empty F-heap, then we can amortize costs such that the amortized
time complexity of each insert, combine, and decrease key operation
is O(1) and that of each delete min and delete is O(log n).
The total time complexity of the entire sequence is the sum of the
amortized complexities of the individual operations in the sequence
</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="text9-index.htm"></map></a></td>
<td width="131"><font face="楷体_GB2312" size="2"><b><a href="text9-25.htm">上一页</a>
<a href="text9-27.htm">下一页</a></b></font></td>
</tr>
</table>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -