[其他] 下三角矩陣相乘的時間複雜度
有兩個nxn的full matrix以及兩個nxn的lower triangular matrix，假設M(n)是兩個
full matrix相乘所需的時間
Mt(n)為兩個lower triangular matrix相乘所需的時間，請問各位如何使用
transformation method來證明Mt(n)=Ω (M(n))?
也就是兩個lower triangular matrix相乘的時間複雜度的lowerbound
跟兩個full matrix相乘的是差不多的，
其中兩個full matrix相乘的lower bound是Ω(n^2)
目前我的想法是將兩個lower triangular matrix 轉換成full matrix
由於
T(lower_triangular_matrix_multiplication(n))+O(lower_triangular_matrix_transformation(n))>=
Ω(full_matrix_multiplication(n)) = Ω (n^2)
也就是
T(lower_triangular_matrix_multiplication(n))>=Ω
(full_matrix_multiplication(n)) -O(lower_triangular_matrix_transformation(n))
所以我需要的只是一個O(n^2)的轉換方法把 lower triangular matrix轉換成full
matrix，並且計算這個部份的時間複雜度
目前我的想法是將將此下三角矩陣(L)的轉換定為L+L'(transpose)，這樣他就變成一個
full matrix，而且矩陣相加跟矩陣轉置的計算量都是O(n^2)，故得證
請問各位大大，我這樣的想法合理嗎?謝謝哦^^
--
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.96.40.70
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1458090780.A.443.html