概略

　自己相関、相互相関が数値計算の基本になっていることが多い。
ここでは前提ごとに計算量の評価をしておき、相関を使う数値計算の基礎資料とする。

計算量の評価

全相関値を求める場合

原型　→　相関計算は、２つの数列（自分自身でも、別のでも）があるとして　An*Bn+k の総和だ。
FFT　→　２つの数列（自分自身でも、別のでも）をフーリエ変換したものについて、共役を乗じて、逆フーリエ変換

原型とFFT形について、数列の長さごとに、全部の相関値を求めるための計算量を比較してみよう。
数列の長さをN（２の累乗にしよう）とすれば

原型　→　N＊N回の積和 FFT　→　N*log(N)のFFT　N回の乗算、N*log(N)回の逆FFT　 　→　2*N*log(N)　のバタフライ＋N回の複素乗算 　→　2*N*log(N) の2*(複素乗算+2*複素加算) + N回の複素乗算 　→　8*N*log(N)+Nの乗算とその2倍の加算乗算について計算したものだ。 これによれば、数列の長さ64からFFT方のほうが計算量が少ない。 keisan1.xls

計算長 original FFT 32 2048 2272 64 8192 5440 128 32768 12672 256 131072 28928

少数の相関係数を求める場合

全項の相関を必要とせず、ひとつまたは数個の既知の相関係数を求めればいいことがある。
このとき乗算回数は32この係数までは、原始的な計算法で求めた方が早い事になる。青色部だよ。

計算長	FFT	1	2	4	8	16	32
64	5440	128	256	512	1024	2048	4096
128	12672	256	512	1024	2048	4096	8192
256	28928	512	1024	2048	4096	8192	16384
512	65024	1024	2048	4096	8192	16384	32768
1024	144384	2048	4096	8192	16384	32768	65536
2048	317440	4096	8192	16384	32768	65536	131072
4096	692224	8192	16384	32768	65536	131072	262144
8192	1499136	16384	32768	65536	131072	262144	524288

..end