21/03/30 13:35:25.16 85330UQl.net
あ、>>499の前半の早くなる理由はウソ
しかし後半が自明でないのはその通りじゃない？
v×wを0埋めして(v,0..)×(w,0‥)の計算がnlog(n)で計算できたとして、目標のv×wの各成分は(v,0..)×(w,0‥)の各成分の高々log(n)個の線形結合になってるの？
計算できるかどうかじゃないよ？
計算量の問題だよ？、
21/03/30 13:35:25.16 85330UQl.net
あ、>>499の前半の早くなる理由はウソ
しかし後半が自明でないのはその通りじゃない？
v×wを0埋めして(v,0..)×(w,0‥)の計算がnlog(n)で計算できたとして、目標のv×wの各成分は(v,0..)×(w,0‥)の各成分の高々log(n)個の線形結合になってるの？
計算できるかどうかじゃないよ？
計算量の問題だよ？、