※ 引述《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