作者FRAXIS (喔喔)
看板Grad-ProbAsk
标题Re: [理工] [algo]-时间复杂度
时间Thu Dec 24 16:19:51 2009
※ 引述《aey (________)》之铭言：
: 证明nxn方阵 A^2 与 (A^T) x A 的时间复杂度相同
: 请问有什麽证法能够参考一下吗 谢谢
假设要做A^2，设计一个新矩阵
A' = [ 0 A^T ]
[ A 0 ]
A'^T = [ 0 A ]
[ A^T 0 ]
A'^T x A = [ (A^T)^2 0 ]
0 A^2 ]
所以我们可以从A^T x A得到一个A^2。
假设要做A^T x A，设计一个新矩阵
A' = [ 0 A^T ]
[ A 0 ]
A'^2 = [ A^T x A 0 ]
[ 0 A x A^T ]
所以我们可以从A^2得到A^T x A。
而且以上两种转换方式都不会影响到时间复杂度，所以此两问题等价。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.119.162.50