计算复杂性

-回复 -浏览
楼主 2020-11-11 10:08:21
举报 只看此人 收藏本贴 楼主


实习15 计算复杂性

 

1. 实验目的

 

1)掌握分析算法复杂度的方法,能够对所编程实践的算法做出复杂度估计。

2)学习并初步掌握查阅相关学术文献的途径,选取恰当的算法解决复杂问题。

3)优化算法,不断提高程序的运行效率和速度。

 

2. 实验内容

 

事先编写好程序,上机调试和运行程序,分析结果。

 

1)求 n阶行列式的值 n阶积和式的值。编程时需要注意:

 

充分利用行列式的定义和性质,提高运行程序进行计算的速度;

查阅有关积和式计算方法的学术文献,选择效率更高的算法;

对于特殊矩阵,比如稀疏矩阵,调研可能存在哪些与之对应的特殊方法,可以用来快速算出它的积和式的值。计算这些特殊矩阵的积和式。

对于不同的n,记录程序运行所需时间,然后分析运行时间与n的关系,

 

n阶方阵A=(aij)的积和式的定义为


 

其中,Ω表示1,2,,n的全排列集合。注意积和式与行列式在定义上的类似与区别。

 

2)定义元素全为01的矩阵为“阴阳矩阵”,即一个nm列的矩阵A为“阴阳矩阵”当且仅当:


 

对于一个nm列的矩阵A和一个nm列(1nn, 1mm)的矩阵A,称AA的子矩阵,当且仅当:

 

 

自然地,“阴阳矩阵”的子矩阵也是“阴阳矩阵”。对一个nm列的“阴阳矩阵”A,称它为“完美阴阳矩阵”当且仅当以下两个条件都成立:



 

显然,一个nm列的矩阵的元素个数为n×m。现给定一个nm列的“阴阳矩阵”A

 

求“阴阳矩阵”A的子方阵(行与列数目相同的子矩阵)中元素最多的“完美阴阳方阵”,输出该子方阵的元素数目。

 

求“阴阳矩阵”A的子矩阵中元素最多的“完美阴阳矩阵”,输出该子矩阵的元素数目。

 

输入的第一行是两个空格隔开的整数nm,分别表示矩阵的行数和列数。接下来的n行,每行输入m个数,空格隔开,表示一个n×m的阴阳矩阵。

 

输出两行,每行一个数,表示所求答案。

 

例如,输入

 

3  3

1  0  1

0  1  0

1  0  0

 

则运行程序时输出

 

4

6

 

3. 预习内容

 

学校图书馆网站上面介绍的常用文献数据库的查阅使用方法。


 打赏 


我要推荐
转发到