📄 text9-21.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">(6)<font color="#FF0000"> analysis</font>
【<font color="#0033CC">definition</font>】 The binomial tree , Bk, of degree k is a tree such that
if k = 0, then the tree has exactly one node and
if k > 0, then it consists of a root whose degree is k and whose
sub tree are B0, B1, …, Bk-1
<i> <font color="#0033CC">insert --</font> <font color="#FF0000">O(1) </font> <font color="#0033CC"> delete -- </font></i><font color="#FF0000"><i>O(logn)</i></font>
〖<font color="#0033CC">Lemma9.2</font>〗Let a be a B-heap with n elements that results from a
sequence of insert, combine, and delete min operations performed
on initially empty B-heap. Each min tree in a has degree <= <img src="image/logn.gif" width="61" height="24" align="middle">.
Conesquencely, MAX_DEGREE <= [<img src="image/logn.gif" width="61" height="24" align="middle"> ] and the actual cost of
a delete min is <font color="#FF0000">O(logn + s )</font>
〖<font color="#0033CC">Theorem9.1</font>〗 If a sequence of n insert, combine, and delete min
operations is performed on initially empty B-heap, then we can
amortize cost such that the amortized time complexity of each insert
and combine is O(1) and that of each delete min is O(log n)
actual cost of any sequence of i insert, c combines, and dm delete
min is <font color="#FF0000">O (i + c + dm log i )
</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="text9-index.htm"></map></a></td>
<td width="131"><font face="楷体_GB2312" size="2"><b><a href="text9-20.htm">上一页</a>
<a href="text9-22.htm">下一页</a></b></font></td>
</tr>
</table>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -