[理工] 演算法-下三角矩陣相乘的時間複雜度
有兩個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，並且計算這個部份的時間複雜度
請問各位大大，我這樣的想法是正確的嗎?謝謝哦
--
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 218.161.26.106
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1457751208.A.DD2.html
推
03/12 18:41, , 1F
03/12 18:41, 1F
→
03/12 18:41, , 2F
03/12 18:41, 2F
推
03/12 19:48, , 3F
03/12 19:48, 3F
→
03/12 19:49, , 4F
03/12 19:49, 4F
→
03/12 19:51, , 5F
03/12 19:51, 5F
→
03/12 19:56, , 6F
03/12 19:56, 6F
→
03/15 13:37, , 7F
03/15 13:37, 7F
→
03/15 13:37, , 8F
03/15 13:37, 8F