楼主:
iasm (I am Nobody)
2016-03-12 10:53:24有两个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,并且计算这个部份的时间复杂度
请问各位大大,我这样的想法是正确的吗?谢谢哦
作者:
FRAXIS (喔喔)
2016-03-12 18:41:00你要的应该是 reduction 吧 利用 lower triangular matrix来计算 full matrix multiplication
作者:
OppOops (Oops)
2016-03-12 19:48:00full matrix的lower bound Ω(n^2), 要给个常数不然以这样的前提reduction function就要比n^2还小随便个矩阵加法至少都要 2*n^2除非lower bound改成 n^2.01 之类的, 不然会证不出来
楼主:
iasm (I am Nobody)
2016-03-15 13:37:00目前想法把L+L',其中L->L'为O(n^2),L+L'也是O(n^2)由于这两者都是O(n^2),故得证^^|