文档介绍：Ｐrim算法与穷举算法的时间复杂度分析
1、基本概念
在一个连通网的所有生成树中,各边的代价之和最小的那棵生成树称为该连通网的最小生成树。
ﻩ最小生成树的性质:
设N=(V,{Ｅ｝) 是一个连通网,Ｕ是顶点集V的一个非空子集,若(u,ｖ)是一条具有最小权值的边,其中ｕ属于U,v属于V,则存在一颗包含边(u,ｖ)的最小生成树。
ﻩＰｒim算法就是利用这一性质来求最小生成树的,与穷举算法相比,Prim算法拥有更好的时间复杂度。
2、两种算法的思想
：
１首先将初始顶点ｕ加入到U中，对其余每一个顶点i,将closedge[ｉ］初始化为到点u的信息。
2 循环n-１次
1)从各组最小边cloｓeｄｇe［ｖ]中选出最小的最小边cloｓedgｅ[k0](ｖ,ｋ0属于V-Ｕ);
2)　将ｋ加入到U中;
3) 更新剩余的每组最小边信息closedｇe[v](v属于V-Ｕ).
对于以v为中心的那组边,新增加了一条从k0到ｖ的边,如果新边的权值比cｌｏseｄge［ｖ].lｏｗcｏst小,则将cｌosｅｄgｅ[ｖ］.ｌowcoｓt更新为新边的权值.
:
1 首先将初始顶点u加入到Ｕ中，其余顶点加入到Ｖ中,ｈ赋值为无穷大
２穷举下列步骤
1) 从U中选择一个顶点a，从V中选择另外一个顶点ｂ
２) 如果两个顶点间的距离不为无穷大,则将b加入到Ｕ中，从Ｖ中移除b，当前权值加上ａ-b的权值
3) 如果V不为空,转到1）,如果Ｖ为空，而且权值比ｈ小，将权值赋值给h

A．Prｉｍ时间复杂度分析
1 n次
２ n次
２ 1)n次
2 2)1次
2 3）n次
Ｔ（n)＝n+ｎ＊(n＋１＋n)
=n+２n^2+n
=2O（ｎ^2)

１　ｎ次
2 (n-１)*1+（n-２)＊2+…+1＊(n－1)　次
2　1)　n次
2 ２）　n次
２ 3) ｎ次
T(n)=n＋(（n-1)*1+(n－2)*2+…+1＊(n-1))*（n+ｎ+n）
<＝n+(n*n+ｎ＊n+…+n＊n)＊3n
　 =n+3n^３
　　 =３O（n^３)
矩阵连乘动态规划算法
1、问题描述
给定ｎ个矩阵｛A1，A2,…,An},其中Ai与Ａi+1是可乘的,i＝1,2，…,n-1。要算出这ｎ个矩阵的连乘积Ａ1A２…An。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用２个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为：
（1）单个矩阵是完全加括号的；
（2）矩阵连乘积A是完全加括号的，则A可表示为２个完全加括号的矩阵连乘积B和Ｃ的乘积并加括号,即Ａ=(BC)。
例如，矩阵连乘积ＡBCD有5种不同的完全加括号的方式:A((BＣ)D),A（Ｂ(ＣD)),（ＡB)(CB)，((ＡB)C)D，(A(BＣ)）Ｄ。每一种完全加括号的方式对