21/03/30 12:31:15.21 1nCYsZUW.net
>>493
なぜゼロつめができないと決めつける？
非巡回畳み込みはゼロつめで高々2倍のnで2^kの計算に持ち込めて定数を無視すると
O(2n*log(2n))=O(n*log(n))で計算できる。
巡回畳み込みは非巡回畳み込みをn回足せばよいだけだからこれもn*log(n)オーダで計算できる。
したがって任意の非巡回、巡回畳み込みはn*log(n)オーダで計算でき、
任意のnの離散フーリエ変換もこのオーダーで計算できる。
またレーダーの方法以外にも素数nの離散フーリエ変換をO(n*log(n))で計算するアルゴリズムは少々技巧的だが存在する。