稀疏图生成树计数-ansi-vita 62-2016 modular power supply standard

时间:2024-06-29 16:21:25
【文件属性】:

文件名称:稀疏图生成树计数-ansi-vita 62-2016 modular power supply standard

文件大小:2.84MB

文件格式:PDF

更新时间:2024-06-29 16:21:25

集训队论文集

4.3 稀疏矩阵的行列式 考虑如何计算行列式det(A),显然如果这个矩阵满足4.1小节中的重要条件,我们就可 以求特征多项式,然后取常数项再乘上(−1)n即可。 假如这个矩阵不满足该条件,我们可以随机一个对角矩阵B,这个的运算次数是O(ne)。 假如数域足够大,那么AB有很大的可能满足这个条件。由于det(AB) = det(A)det(B),我们 只需要计算det(AB),并除以det(B)即可。由于B是对角矩阵,det(B)就是B矩阵对角线上的元 素的乘积。 于是,我们得到了可以在O(n(n + e))次运算、关于矩阵大小是线性的空间内计算稀疏矩 阵的行列式的蒙特卡罗算法。 4.4 稀疏图生成树计数 显然,生成树的个数可以利用基尔霍夫矩阵树定理计算。假如这个图足够稀疏,那么 拉普拉斯矩阵的行列式显然可以用4.3小节中的方法计算。 这个算法的时间复杂度是O(n(n + m)),空间复杂度是O(n + m),十分优秀。 5 总结 本文全文均围绕递归式展开,第一部分讲述了递归多项式,第二部分研究了Berlekamp- Massey算法,第三、四部分主要介绍了它们的一些应用。 我希望这篇文章能起到抛砖引玉的作用。本文仍然是对递归式的不成熟研究,介绍的 应用也都比较基础,而科技在不断进步,一定还有更多有趣的应用等着我们去发现。因此, 愿此文能对读者有所启发,引出一些更加炫酷的应用。 鸣谢 1. 感谢杜瑜皓同学,我最早是从他口中听说的这个算法,且本文中部分内容的出现离 不开他的帮助。 2. 感谢杜瑜皓同学,杨家齐同学与翁文涛同学的纠错。 3. 感谢中国计算机学会提供学习和交流的平台。 参考文献 [1] * 10


网友评论