算法的复杂性分析

1、数值实验02:算法的复杂性分析自动化系 孟强2009310517一个n xn矩阵A = av 的积和式的定义nperm(A) = Z n(l)其中A”表示由1,2,."所有排列构成的集合。从定义上看矩阵积和式和行列式 非常相似，但是计算积和式的难度远远超过行列式。对一般的nxn矩阵，已知最 好的算法需要O(n-2n)计算量NW78。对于稀疏等具有一定结构的矩阵，利用结 构特性可能给出更有效的积和式算法。本实验研究算法的复杂性问题，特别是平 均意义下的复杂性。基本问题(验证，性的)1.仿照矩阵行列式的Laplace展开，建立并证明积和式的Laplace展开.直接用积 和式的Laplac

2、e展开作为计算方法，试讨论其计算复杂度。注意到该算法是递 归的，所以算法的存储(即空间复杂度)需要特别关注。定义积和式的Laplace展开：设在行列式A中任意取定了 ±(1 SArSn-1)行，由 这£行元素所组成的一切上级子式与余子式的乗机之和等于行列式的积和式。证明设a中取定V行后得到的子式为4，心.，4,它们的余子式分别为M'M由引理(行列式A的任一个子式与它的代数余子式的乘积中的每一项都是行 列式A的展开式中的一项，而且符号也一致)可知，不考虑符号的影响，上述引理 一样成立，即：行列式A的任一个子式与它的余子式的乘积中的每一项都是行列 式A的积和式中的一项。

3、因刀4胚中共有C>!(m -Zr)!=:上!(n -七)!二川项，且人皿；与AM,i-ik'.Qi -(i H j)无公共项。由积和式的定义可以看出，矩阵的积和式中共有川。因此，证毕。计算复杂性直接用积和式的Laplace展开作为计算方法，其算法的复杂度可以从时间复 杂度以及空间复杂度两个方面来分析。时间复杂度：该直接算法中，矩阵的积和式共有川项，而每一项中包含(n-1)次的乘法， 因此，其总共的乘法运算次数为(n-l)n!次。加法总共有(n-1)次，而加法相对乘 法可以忽略，因此，之后的分析中只对比乘法的运算次数。空间复杂度：从三个方面进行分析：算法本身所占用的内存，算法的输入

4、输出数据占用的 内存，算法在运行过程中占用的存储空间。假定按第一行展开，釆用递归的方式，每次递归压栈主要空间可认为是 0?-1)3, (n - 2)2, 07-3)2F,而递归重数为n ,因此，其空间复杂度应该为： (/? -I)3 +.I2运算矩阵为nxn矩阵，算法的输入输出矩阵占用的存储空间可近似是为n2 相对前两项，忽略算法本身占用的内存，则总的空间复杂度可近似为 n2 + (n-l)2 +.I3 = <9(/?3)2.计算机程序实现积和式的Laplace展开算法和矩阵行列式的Laplace展开算 法。设计完成至少10纽实验，实验的参数是矩阵的规模和矩阵的稀疏性(计 算矩阵的规模尽

5、可能大并适当稀疏)。分析实验结果并讨论上述两个算法的 复杂度(包括空间复杂度)°编程实现该算法，检测元素是否非零，如遇到农元素跳出递归运算。由于针 对生成的不同矩阵，每次运算的时间有一定差距，因此，比较积和式与行列式运 行时间时，针对同一矩阵进行分析，以便于比较与分析取儿纽参数如表Table 1.1, n = ll,4regidar表示阶次为12,且Aregidar的矩阵。(由于计算程序峰值内存的运 算也会占用一定的运算时间，因此，运行时间及峰值内存计算分别通过两个程序 完成，见附录程序2. 1及附录程序2. 2(profile) °Table 1.1积和式与行列式比较实

6、验 次 数矩阵阶数及稀疏 性积和式行列式运行时间峰值内存运行时间峰值内存1n = 12.4regiilar0. 719122880.766122882n = 12.5regidai 4. 36122884. 782122883n = 2,6regidar20.6251228822. 063122884n = 12.1 regular86. 84420480 (12288)93.57932768 (16384)5n = 12regitlar296.68720480(24576)326.656163846n = 13,4regular1.437122881.54712288# 7n = 14.4r

7、egidar3. 31312288 (16384)3.593122888n = 15.Aregttlar6. 2031 22886.672122889n = 16.4regidai 13. 9061 228814. 751228810n = 17.regular22. 0161228822. 81212288数据分析：由Able 1.1可以看出，对于同一个矩阵而言，应用Laplace展开算法，其 积和式与行列式的计算时间差别很小，应该仅仅相差符号运算的时间。各次数据 的峰值内存几乎不变化，或者说有波动，其可能的原因是仿真的矩阵阶次太小， 并不能得到有意义的结论。因此，该峰值内存的数据不能作为有

8、效的分析数据。 以下重点分析当矩阵规模及稀疏性变化时，积和式运算时间复杂度的变化.实验数据15可以看出，对于12的矩阵，当其沧g"茁由4逐渐变为8时， 其运算时间增长很快，但其增长倍数均在同一数量级，依次大概为6、4.7、4.2、 3.4;对比实验数据1、610可看出，如果矩阵的regular均为4,矩阵规模由12 逐渐变为17时，其运算时间大概每次变为前次的2倍。这是一个非常有用的发现。以此可得出一个小的结论，即矩阵阶次对计算复杂度的影响应该表现在指数 上，而且其底数可能为7锣a严。为进一步验证上述结论，再做一下几纽实验进行校核。Table 1.2积和式运算吋间实验 次数矩阵阶数及

9、稀疏性积和式运行时间积和式数值1n = 9,6regular0.8120120722n = 10.6regtdar2. 3910304683n = 11.6regidar7.078764164n = 12,6regidar20.6251941965n = 3.6regidar65. 12504754966n = .6regular178.875012032047n = 15.6regi tlar517.于本实验矩阵釆用0-1矩阵，因此，其积和式的值即为展开式中能最终运 算到最后的总排列数。当然，更多的排列在取到n-1.1个值时就停止运算。但是，通过分析积和式值的变化规

10、律，可以大概估测整体计算复杂度的变 化。对比数据Table 1.2中数据可以看出，对t regular = 6的矩阵，当其规模由9 变为15时，枳和式每次变为前一次的regular05 = 605 = 2.449倍左右。积和式的时间复杂度：假定矩阵为m-regular的矩阵，即矩阵每行每列中只有血个元素非零，则只关注其中的乘法运算，可知其总共的乘法运算次数肯定小于力”；但是此公式中 当加足够大时，其会超过川，由之前分析知道，当矩阵元素全非零时，其乘法 运算次数为(，7-1加!次。因此，可知，其时间复杂度肯定小于mino(”),o(n!) 可以看出，越稀疏的矩阵，釆用该方法，其计算的时间复杂度降

11、低的越快。由数据分析可以看出，如果当矩阵阶次足够大，而又相对较稀疏时(加 其计算的复杂度有可能可降为O(mn,2)。积和式的空间复杂度：该算法中，虽然递归的重数减小，但是每次递归压栈主要空间仍为0?-1)2, (n-2)2, (n-3)2.l2；输入输出矩阵占用的存储空间近似是为用；因此，总的 空间复杂度应近似认为O(n3)行列式的时间复杂度与空间复杂度：由于编程实现时，行列式与积和式的Laplace展开算法仅仅相差一个符号运 算，其增加的计算量相对于其他计算量可忽略不计，因此，可认为行列式Laplace 展开算法的时间复杂度与积和式的时间复杂度在同一数量级上；而空间复杂度则 完全一致。空间复

12、杂度验证：由上述计算数据可以看出，釆用n-regular的矩阵进行空间复杂度数值计算 时，由于其可计算的矩阵阶次很小，很难将有用信息从各种干扰要素中提取出来, 因此，应该想办法尽量增大矩阵阶次。以下采用对角阵来进行空间复杂度验证。 其程序见附录程序2. 3(profile).矩阵阶数从1取到450,可以得到积和式、行列式的空间复杂度随矩阵阶次增 大的变化情况，见Fig.l ,Fig.2.积和式空树芟杂度分析18(<CCCC1CCC# -# -°o501001 5020025030C350400450500地障阶次Fig.l行列式空间复杂度分析# -18°0250100

13350400450500业障附次Fig.2积和式空间晁杂度分析6 4 2 0 8 6 44 1 1 1CMWW2E空磧二巨卩由Fig.l,Fig.2可以很直观的看出，矩阵积和式与行列式的空间复杂度几乎完 全一致。但是，mem/nT随着n的增大越来越趋近于一个常数，却与理论分析的结 果不一致。修改程序，应用memory进行空间复杂度计算(见程序2.4),得到仿真曲线见 Fig3,Fig4行列式空河复杂度分析5.54W3.5251.543.2 1 oC WEE里 wnNJP100150200250300350400450矩阵阶次500500Fig.3行列式空间复杂度分析(m

14、emory)500积和式空间复杂度分析.54 s 3 s 2.54.3 21.CU.UJE辺恐二色(1)0# (1)0# 0.5100150200250300350400450500矩阵阶次Fig.4积和式空间复杂度分析(memoiy)由此可验证，矩阵积和式和行列式的空间复杂度均可近似为(9(/?3) o可以看出，只有当矩阵阶次很大的时候，才可以通过数值计算近似估计空间 复杂度。而且采用profile与采用memory两种方法得到的空间复杂度的结论不同， 而memory的结论与理论分析结果相同。因此，应该采用memory程序进行空间复 杂度分析。但是对于阶数较低的矩阵，采用上述两种方法都存在很

15、大的波动及不 稳定性，因此，对低阶问题两者都不适用。而本报告已经就以下几个问题采用 profile方法分析，虽然可能不准确，但是却能大体反映趋势。因此，已釆用 profile方法得到数据不进行修正。实验问题(扌采索性的)将nxn矩阵虫写为如下分块的形式a b xy y2 z,其中d和b是两个数字标量，*了是一个(m2)维行向量、.力和旳是两个(n-1)维列 向量，剩下的部分Z是(n-l)x(/7-2)矩阵。则有perm(A) = permf a b xT>畀 y2 z,=perm0 xTy2 z¥ perm(ay2by2 Z)(1)0# 当A非常稀疏时，利用上述的公式(1)计算

16、积和式可能比经典方法更有效。(1)0# 我们将这种方法称为双元素Laplace展开法。3.计算机程序实现积和式的双元素Laplace展开算法，这里同样要注意到该算法 是递归的。试比较直接Laplace展开法与双元素展开法的计算复杂度。设计并 完成至少10组实验，实验的参数是矩阵的规模和矩阵的稀疏性（计算矩阵的 规模尽可能大并适当稀疏）。分析实验结果并讨论算法的复杂性。程序分析采用网络学堂中提供的程序去实现双元素Laplace展开算法，其编程逻辑如 下（其运行时间、峰值内存程序与上题类似，不再给出）：若矩阵A的规模n<6 ,采用RNW方法运算；当并6时，检测矩阵A的行列中每行、每列中非零元

17、个数，并将非零元个数 最小的行或者列转换为行，以便于之后对行展开.再分情况展开：如果该行中非 零元个数为1,则采用直接Laplace展开算法；如果该行中非零元个数为2,则采 用双元素Laplace展开算法；如果该行中非零元个数为3,则其中两个非零元釆用 双元素Laplace展开算法，而另一个非零元釆用直接Laplace展开算法；如果该行 中非农元个数为4,则分别对第1、2及第3、4非零元分别釆用双元素Laplace展开 算法运算；如果非零元个数大于5,则采用RNW方法。由以上的算法可以看出，对于n <6的矩阵，以及regular »5的矩阵，其运 算初始阶段与RNW方法一致；但

18、是随着递归的进行，递归后矩阵的阶数降低并 越来越稀疏，这样，才能更大的突出双元素法的优势。实验数据为便于比较，做以下实验见Table2.1,Table2.2。由于在计算下列数据时，峰 值内存同样很不稳定，要么是零，要么就大概为12288,因此，其同样不具有参 考价值，下表中不再给出.关于空间复杂度的分析将在本题最后讨论。Table2.1积和式的直接法与双元素法比较实验 次数矩阵阶数及 稀疏性直接展开法双元素展开法运行时间运行时间1n = 12,AregiUar0. 7340. 00172n= 12,5regtdai 4. 5620. 00233n = 12,6regidai 22. 2810.

19、 00204n = 12,7 regular88. 9690. 00225n=12,Sregiilai 304.50. 00226n= Irregular1. 68?0. 00207n = 14,Aregiilar3. 3130. 00338n = 15.Aregidar7. 1560. 00339n =13. 1250. 004410n-Yl regular29. 6250. 0040Dble2.2双元素法运算时间实验 次数矩阵阶数及 稀疏性双元素展开法运行时间1n = 26,3regiilar n = ll.iregnlar n = 28 egulai0. 109Fail0. 1252n

20、= 26,4regular n = ll.Aregidar n = 2&regular n = 29.4regular n = 30、4regula】 n = 31,4regiilar10.625012. 703016. 125041. 172043. 031067.89003n = 26y5regtdar n = 27.5regular n = 2,5regidar442. 4680379. 187441.7970数据分析：由Table 2.1可以看出，对于n较大的矩阵，采用双元素法比采用直接 Laplace展开算法的运算时间小很多，并不只是儿个数量级的问题，并且随着矩 阵规模的增大

21、，这种差别也越来越明显.采用该算法中，对于矩阵运算的不同阶段，其釆用的运算方法及复杂度都会 变化，因此，很难单纯对一个特定矩阵，分析其运算复杂度。而以下仅针对程序 实现过程中的处理方式进行分析，以得到关于双元素展开法的一些结论。双元素展开法的时间复杂度与空间复杂度考虑矩阵运算过程中，如果展开行中非零元个数为2,釆用双元Laplace展 开算法，一个上阶矩阵被分解为一个（土-1）阶阵，而直接Laplace展开算法则会产 生两个（七-1）阶阵。因此，双元素法会比直接展开法的时间复杂度减小1/2,并 且此时，两者的堆栈深度相同，即空间复杂度近似相等。如果该行中非零元个数为3,其中两个非家元采用双元素

22、Laplace展开算法， 另一个非农元采用直接Laplace展开算法。此时，一个片阶矩阵被分解为；两个 （土-1）阶阵，并分别递归。因此，此时该算法的时间复杂度变为直接法的2/3倍, 但是递归变为两个，空间复杂度则变为直接法的2倍。如果该行中非零元个数为4,则分别对第1、2及第3、4非零元分别采用双元 素Laplace展开算法运算。此时，一个上阶矩阵被分解为两个（十-1）阶阵，并分别 递归。因此，此时该算法的时间复杂度变为直接法的2/4 = 1/2倍，但是递归变 为两个，空间复杂度则变为直接法的2倍。因此，可以看出，虽然双元素法的时间复杂度较直接法有很大简化，但是却 是通过牺牲空间复杂度来实现

23、的。所以，在实际运算中，要综合考虑其优缺点， 进行选择。9 -4.特别讨论实际应用中一类特殊的稀疏矩阵一-3-regular矩阵（即每行每列都恰 好包含3个非零元素的矩阵），分析研究双元素展开法的计算复杂度，并与算 法NW78的计算复杂度O（n2”）进行对比。由于出作业说明前，我已经针对对称3-regiilar矩阵进行分析，因此，以下分 别针对对称3-regular矩阵以及非对称3-regular矩阵进行实验。对称3-regular矩阵程序分析由于对于不同的矩阵，程序实际运行的时间有一定的差别，而该双元素法及 NW78运算时间都比较短，因此，为准确起见，对于不同阶次及稀疏程度的矩阵， 采取多次

24、运算求平均值的方式（程序见附录程序4. 1）,得到数据如下表Table 3所 示。一般取10组，求其平均值。其中，增长倍数一栏给出的是每次实验运行时间 与前次实验运行时间的比值。对于空间复杂度的数值计算，由于此时矩阵阶次较大时仿真时间太长，而本 题矩阵阶次最高仅到70,由第二题中釆用memory及profi le两种方法的分析中可 知，对于该小规模矩阵，空间复杂度儿乎不能采用它们进行分析。本题只仿真儿 组数据，见Dble4.Table3积和式NW78法与双元素法比较（3-regular矩阵）实验 次数矩阵阶数双元素展开法NW78 法运行时间增长倍数运行时间增长倍数1n =100. 00140.

25、 00552n=120. 0021. 420. 02163933n =140. 0031. 50. 08664. 014=160. 0041. 330. 36754. 245n = 180. 0071. 751. 52974. 166n = 200. 0111.576. 38284. 177= 220.01671. 5126. 20944. 118n = 240. 02721.57106.21854. 059n = 260. 04281. 5710n = 300. 1152.6911n = 401. 212410. 5412n = 5016. 918813.9513n = 60298.2351

26、7. 62714n = 70451015. 134Table4积和式NW78法与双元素法比较（3-regular矩阵）实验 次数矩阵阶数及 稀疏性双元素展开法NW78 法峰值内存峰值内存1« = 421.1878X1042n = 44122883n = 461.5155 xlO44n = 481.5974 xlO45n = 502.4166X104数据分析：由Table4可看出，此时通过数值分析方法进行空间复杂度分析并不能得到 有效地结论。由Table3可以看出，采用双元素法比采用NW78算法的运算时间小很多，并 不只是几个数量级的问题，并且随着矩阵规模的增大，这种差别也越来越明显。

27、观察Table 3中，采用NW78法时，平均运算时间以及增长的倍数可以发现， 当矩阵规模由n = 10依次增大到z? = 24时，其阶数每增加2,运行时间会变为之前 的4倍多一点，这与其计算复杂度不谋而合。因为已知其计算复杂度为O仟2”）， 其阶数每增加2,运行时间会变为之前的4倍多.所以，当所取的实验数据足够大 时，通过运算时间的变化规律即可大致看出其计算复杂度的变化规律。仔细观察Able 3中双元素展开法的运行时间及增长倍数可以发现，当矩阵规 模由« = 10依次增大到? = 24时，其计算时间的变化倍数也大概为一常数，大致 为1.5左右。但是由于计算机运行时，由于其他程序占用的

28、内存可能存在波动以 及其他一些影响，仅仅分析临近数据变得不很可靠。如果矩阵阶次对于该算法的 复杂度影响是位于指数级别上的，那么阶次相差越大的项对比，得到的结论就越 准确。釆用公式（几1/：尸八心来分析，其中，几表示当矩阵阶次为2时，其运算 时间。取皿=20/2 =10时,取泌=30/2 = 20时,取/?1 = 50/2 = 20 时,取ml = 70/2 = 20 时,由此可以看出，其运算复杂度可能为：OQ.25”）-11非对称3-regular矩阵编写一般非对称regular矩阵程序（见程序4.2）,针对矩阵阶数由6-40,绘制双 元素法计算复杂度与心沪及1.25”相除后的曲线见下图（见程

29、序4.3）.仪兀庶法if徉复冬度分析005101 52025303540矩降阶次na）计算复杂度0.160.140.120.04 、0.02 -05101 52025303540矩阡阶次nb）计算复杂度/nc）计算复杂度/n八2d）计算复杂度/n八3 13 X10-3戏元索法计口复杂度分析1.2、0.2 # #°o101 52025303540如阡阶次ne)计算及杂度/1.25八iiFig.5双元素法计算复杂度分析(3-regular)由以上分析可以看出，对于双元素法的计算复杂度肯定不能通过0(，)来表 示，而釆用0(1.25”)来表示可以在一定程度上逼近真值，因此，在一定程度上验

30、证了上述结论。其可能更接近于0(0.7 xlO-3xl.25M).自动化系孟强20093105172009年11月18日星期三附录程序2.1:运行时间计算程序n=13;k=6;m=10;a=syinniRegiil ar(n,k,m);tic;laplace_perm(a)%laplace_det(a)toe;程序2.2:空间复杂度计算程序(profile)n=13;k=6;m=10;a=syinniRegiil ar(n,kjn);profile -memory on;y=laplace_det(a);state=profile(tiiifor);tot_time=state.Functio

31、nTable.Totalrnme; tot_mem=state.FunctionTable.TotalMemAllocated; peak_mem=state.FunctionTable.PeakMem; profile off;程序2. 3:空间复杂度验证程序(profile)mem=;for i=l:90n=i*5;a=ciiag(rand(l ,n);profile memory on;y=laplace_det(a);亍列式 Laplace 展开%y=laplace_penn(a);% 枳和式 Laplace 展开state=profil e(tiiifor); tot_time=st

32、ateFimctionTableTotanime;tot_mem=state.FunctionTable.TotalMemAllocated; peak_mem=state.FunctionTable.PeakMem;profile off;mem(i)=peak八 3;nl(i)=n;%行列式Laplace展开 剜亍列式Laplace展开end plot（nl jnem）;title。行列式空间复杂度分析）； %title（f积和式空间复杂度分析*）;xlabelC矩阵阶次丁；yiabel(，空间复杂度mem/n八3丁;程序2. 4:空间复杂度验证程序(memory)foi i=l:99n=

33、i*5;%a=diag(rand(l)；%a= SPRAND(nji,0.004); a=eye(n);% det jn em =laplace_det(a);peimjnem=laplace_perm(a); nuii(i)=mem/nA3;nl(i)=n;endplot(nl jnm);%title(*行列式空间复杂度分析*)； titled积和式空间复杂度分析)； xlabelf矩阵阶次丁;ylabelC空间复杂度mm/n八3丁；程序4.1：积和式NW78法与双元素法运算时间比较time=0;for i=10k=3;11=60;111=10;a=symmRegiil ar(n,k,m)；

34、tic;Hpenn(a);elapsed_time=toc;time =elapsed_time+time;endtime=time/10;%tic;RNW_penn(a);toc; 15程序4.2:生成一般tegul ar矩阵程序fimcti on A=unsyinmRegul ar(n,k)A=zeros(n);ifk>nfprintf(rhiput enor!please make sure kvJ； return;elseif k=nA=ones(n);return;elseif k=lA=eye(n);return;endwliile 1A=syinmGen(nJ<*on

35、es(l)；if mod(n*k)=0b= sum (sum (A)=k* ones( 141); ifb=iiretimi;endelsea=siim(A);ai-ak;r=find(ar); sizei-length(r); if sizer=lif a(r)=(k-l)A(ra)=l ；elsecontinue;endelsecontinue;endb=siim(siim(A)=k* ones(l 41)；if b=nretiini;endendendend程序4.3:双元素法计算复杂度分析（图表）time=;T=0;for n=6:40for i=l:5k=3;a=unsyiiuiiRegul ar(njc);tic;Hpenn(a);elapsed_time=toc;T=elapsed_time+Ti endtime(n)=T/(5 *1.25 An);nl (n)=n;endplot(nl.tiine);titled双元素法计算复杂度分析*); xlabelf矩阵阶次/n*);yl abe