有两个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)，故得证^^|