有兩個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，並且計算這個部份的時間複雜度
請問各位大大，我這樣的想法是正確的嗎?謝謝哦

你要的應該是 reduction 吧 利用 lower triangular matrix來計算 full matrix multiplication

full matrix的lower bound Ω(n^2), 要給個常數不然以這樣的前提reduction function就要比n^2還小隨便個矩陣加法至少都要 2*n^2除非lower bound改成 n^2.01 之類的, 不然會證不出來

目前想法把L+L'，其中L->L'為O(n^2)，L+L'也是O(n^2)由於這兩者都是O(n^2)，故得證^^|