text5-56.htm
来自「浙江大学计算机学院数据结构课程的教学课件」· HTM 代码 · 共 47 行
HTM
47 行
<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">第五章</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 align="left"><font face="Arial, Helvetica, sans-serif" size="4" color="#000000"><b>
3. <font color="#FF0000">Matrix Multiplication
</font>
<i><font color="#0033CC">M 1 * M 2 * .... * M n </font></i>
matrix multiplication is associative
n =3 : two possibilities: <i><font color="#0033CC">( M 1 * M 2 ) * M 3
M 1 * ( M 2 * M 3 )
</font></i>n = 4: five possibilities: <i><font color="#0033CC">(( M 1 * M 2 ) * M 3 ) * M 4
(M 1 * ( M 2 * M 3 ) )* M 4
M 1 * (( M 2 * M 3 ) * M 4 )
</font></i><i><font color="#0033CC"> (M 1 * ( M 2 * ( M 3 * M 4 ) )) </font></i>
<i><font color="#0033CC">(( M 1 * M 2 ) * (M 3 * M 4))</font></i>
<i><font color="#FF0000">b n </font></i> ----- the number of different ways to compute the product
of n matrices ( b 1 = 1, b 2 = 2, b 3 = 5)
<i><font color="#FF0000">M ij </font></i> = the product <i><font color="#0033CC">M i * M i + 1 * ... * M j</font></i> ( i <= j )
<i><font color="#FF0000">M 1n </font></i> = the product <i><font color="#0033CC">M 1i * M i+1</font></i>, n ( 1 <= i <= n)
M <font size="3">1i </font>= b<font size="3"> i </font> M <font size="3">i+1</font>, n = b <font size="3">n - i </font>
<img src="IMAGE/text5-z17b.gif" width="150" height="36">
b n = the number of distinct binary trees with n nodes
b n = the sum of all the possible binary trees formed in the
following way:
a root and two subtrees with b i and b n - i-1 nodes,
for 0 <= i <= n
<img src="IMAGE/text5-z15.gif" width="185" height="103"> <img src="IMAGE/text5-z16.gif" width="235" height="39">
</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="text5-index.htm"></map></a></td>
<td width="131"><font face="楷体_GB2312" size="2"><b><a href="text5-55.htm">上一页</a>
<a href="text5-57.htm">下一页</a></b></font></td>
</tr>
</table>
</body>
</html>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?