作者iasm (I am Nobody)
看板Grad-ProbAsk
標題[理工] 演算法-下三角矩陣相乘的時間複雜度
時間Sat Mar 12 10:53:24 2016
有兩個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
推 FRAXIS: 你要的應該是 reduction 吧 利用 lower triangular matrix 03/12 18:41
→ FRAXIS: 來計算 full matrix multiplication 03/12 18:41
推 OppOops: full matrix的lower bound Ω(n^2), 要給個常數 03/12 19:48
→ OppOops: 不然以這樣的前提reduction function就要比n^2還小 03/12 19:49
→ OppOops: 隨便個矩陣加法至少都要 2*n^2 03/12 19:51
→ OppOops: 除非lower bound改成 n^2.01 之類的, 不然會證不出來 03/12 19:56
→ iasm: 目前想法把L+L'，其中L->L'為O(n^2)，L+L'也是O(n^2) 03/15 13:37
→ iasm: 由於這兩者都是O(n^2)，故得證^^| 03/15 13:37