\u97f3\u58f0\u51e6\u7406\u307e\u308f\u308a\u306e\u77e5\u898b\u3092\u8abf\u3079\u305f\u3002\u30a4\u30f3\u30d1\u30eb\u30b9\u5fdc\u7b54\u306e\u7573\u307f\u8fbc\u307f\u306f\u3084\u3063\u3071\u308aFFT\u3092\u4f7f\u3046\u306e\u304c\u666e\u901a\u3089\u3057\u3044\u3002\u7573\u307f\u8fbc\u307f\u3092O(N^2)\u304b\u3089O(NlogN)\u306b\u843d\u3068\u3059\u306b\u306f\u305d\u308c\u3057\u304b\u306a\u3044\u308f\u306a\u3002<\/p>\n\n\n\n
\u306a\u3093\u304b\u6ce2\u5f62\u306e\u533a\u9593\u3092\u5207\u308a\u53d6\u3063\u3066FFT\u304b\u3051\u308b\u3068\u3044\u3046\u8a71\u3092\u3059\u308b\u3068\u3069\u3046\u3082\u7a93\u95a2\u6570\u306e\u8a71\u304c\u51fa\u3066\u304f\u308b\u3002\u3057\u304b\u3057\u3001\u30b9\u30da\u30af\u30c8\u30e9\u30e0\u304c\u898b\u305f\u3044\u306e\u3067\u306f\u306a\u304f\u7573\u307f\u8fbc\u307f\u3092\u3057\u305f\u3044\u3068\u3044\u3046\u76ee\u7684\u3067FFT\u306a\u3089\u7a93\u95a2\u6570\u306f\u8981\u3089\u306a\u3044\u306e\u3067\u306f\u306a\u3044\u304b\u3002\u306a\u3093\u304b\u8a08\u7b97\u3057\u3066\u307f\u305f\u611f\u3058\u3084\u3063\u3071\u308a\u305d\u3093\u306a\u611f\u3058\u3060\u3063\u305f\u3002<\/p>\n\n\n\n
\u5468\u6ce2\u6570\u9818\u57df\u3067\u639b\u3051\u7b97\u3092\u884c\u3046\u3068\u6642\u9593\u9818\u57df\u3067\u306f\u7573\u307f\u8fbc\u307f\u306b\u306a\u308b\u306e\u306f\u5e38\u8b58\u3068\u3057\u3066\u77e5\u3063\u3066\u3044\u305f\u304c\u3001\u8a73\u7d30\u306a\u6319\u52d5\u304c\u3069\u3046\u306a\u308b\u306e\u304b\u826f\u304f\u628a\u63e1\u3057\u3066\u3044\u306a\u304b\u3063\u305f\u306e\u3067\u624b\u3092\u52d5\u304b\u3057\u3066\u5b9f\u9a13\u3057\u305f\u3002N=4\u306e\u3068\u304d\u3001\u4fe1\u53f7$s_0,..s_3$\u3068\u30a4\u30f3\u30d1\u30eb\u30b9\u5fdc\u7b54$h_0,…h_3$\u3092\u7573\u307f\u3053\u3082\u3046\u3068\u3059\u308b\u3068\u3053\u3093\u306a\u611f\u3058\u306b\u306a\u308b\u3002<\/p>\n\n\n\n
$\\mathbf{\\hat{s}}=\\mathbf{Fs}$<\/p>\n\n\n\n
$\\mathbf{\\hat{h}}=\\mathbf{Fh}$<\/p>\n\n\n\n
$\\mathbf{F^{-1}}\\left(\\begin{array}{c}\\hat{s}_0\\hat{h}_0 \\\\ \\hat{s}_1\\hat{h}_1 \\\\ \\hat{s}_2\\hat{h}_2 \\\\ \\hat{s}_3\\hat{h}_3\\end{array}\\right)=\\left(\\begin{array}{c}s_0h_0 + s_1h_3 + s_2h_2 + s_3h_1 \\\\ s_0h_1 + s_1h_0 + s_2h_3 + s_3h_2 \\\\ s_0h_2 + s_1h_1 + s_2h_0 + s_3h_3 \\\\ s_0h_3 + s_1h_2 + s_2h_1 + s_3h_0\\end{array}\\right)$<\/p>\n\n\n\n
\u6b8b\u5ff5\u306a\u304c\u3089\u3001\u5468\u671f\u7684\u306b\u306a\u308b\u306e\u3067\u3053\u306e\u3088\u3046\u306b\u4f59\u8a08\u306a\u9805\u304c\u5165\u3063\u3066\u3057\u307e\u3046\u3002\u4e0a\u8a18\u306e\u5f0f\u3067\u8a00\u3046\u3068\u3001\u6700\u53f3\u8fba\u306e\u53f3\u4e0a\u306e\u90e8\u5206\u306f\u4e38\u3063\u3068\u8981\u3089\u306a\u3044\u3002$s_0h_0$\u306e\u5f8c\u308d\u306e$s_1h_3 + s_2h_2 + s_3h_1$\u3068\u304b\u3092\u524a\u308a\u305f\u3044\u3002<\/p>\n\n\n\n
\u3053\u306e\u4f59\u8a08\u306a\u90e8\u5206\u3092\u9664\u304f\u306b\u306f\u4f55\u3092\u3059\u308c\u3070\u3044\u3044\u304b\u3068\u8003\u3048\u308c\u3070\u3001h\u3068s\u306e\u5f8c\u308d\u534a\u5206\u306e\u8981\u7d20\u30920\u306b\u3059\u308c\u3070\u3044\u3044\u3053\u3068\u304c\u5206\u304b\u308b\u3002\u9006\u306b\u8a00\u3048\u3070\u3001\u4f7f\u3044\u305f\u3044\u30a4\u30f3\u30d1\u30eb\u30b9\u5fdc\u7b54\u304c\u3042\u308b\u306a\u3089N\u3092\u305d\u308c\u306e2\u500d\u306b\u8a2d\u5b9a\u3057\u3066\u5f8c\u308d\u534a\u5206\u30920\u3067\u57cb\u3081\u308c\u3070\u3044\u3044\u3002\u305d\u3046\u3059\u308b\u3068\u4e0a\u306e\u5f0f\u304b\u3089\u5e73\u884c\u56db\u8fba\u5f62\u307f\u305f\u3044\u306a\u90e8\u5206\u304c\u6b8b\u308b\u3002\u3053\u308c\u3067\u9806\u6b21\u5207\u308a\u53d6\u3063\u3066\u306fFFT\u3092\u4f7f\u3063\u305f\u7573\u307f\u8fbc\u307f\u3092\u884c\u3063\u3066\u8db3\u3057\u3066\u3044\u3051\u3070\u3088\u3044\u3002<\/p>\n\n\n\n
\u7a93\u306e\u5927\u304d\u3055\u3092$N$\u3001\u97f3\u58f0\u30c7\u30fc\u30bf\u5168\u4f53\u306e\u9577\u3055\u3092$L$\u3068\u3059\u308b\u3068\u3001FFT\u3092\u884c\u3046\u56de\u6570\u306f$O(L\/N)$\u30671\u56de\u3084\u308b\u3054\u3068\u306b$O(N)$\u56de\u306e\u639b\u3051\u7b97\u3068\u8db3\u3057\u7b97\u3092\u884c\u3046\u3002\u306e\u3067\u5168\u4f53\u306e\u8a08\u7b97\u91cf\u306f$O(L\/N(N\\log N+N))=O(L\\log N)$\u306b\u306a\u308b\u3002<\/p>\n\n\n\n
\u3068\u3053\u308d\u3067\u3001\u30a4\u30f3\u30d1\u30eb\u30b9\u5fdc\u7b54\u304c\u6cbb\u307e\u308b\u3088\u3046\u306b$N$\u3092\u5b9a\u3081\u308b\u306e\u3060\u3068\u3059\u308b\u3068\u3001\u6700\u4f4e\u3067\u3082\u30a4\u30f3\u30d1\u30eb\u30b9\u5fdc\u7b54\u306e\u9577\u3055\u3060\u3051\u306e\u9045\u5ef6\u304c\u8d77\u304d\u308b\u3053\u3068\u306b\u306a\u308b\u3002\u3053\u308c\u306f\u5834\u5408\u306b\u3088\u3063\u3066\u306f\u8a31\u5bb9\u3067\u304d\u306a\u3044\u3002\u305d\u3053\u3067\u3001\u30a4\u30f3\u30d1\u30eb\u30b9\u5fdc\u7b54\u306e\u9577\u3055\u3092$M$\u3068\u3057\u3001$C$\u5206\u5272\u3057\u3066\u7a93\u306e\u9577\u3055\u3092$M\/C$\u3068\u3059\u308b\u3053\u3068\u3092\u8003\u3048\u308b\u3002\u7a93\u306e\u5207\u308a\u53d6\u308a\u306f$L\/(M\/C)=CL\/M$\u56de\u3042\u308a\u30011\u56de\u3054\u3068\u306b\u5927\u304d\u3055$O(M\/C)$\u306eFFT\u3092$O(C)$\u56de\u3001$O(C\\times(M\/C))=O(M)$\u56de\u306e\u639b\u3051\u7b97\u3068\u8db3\u3057\u7b97\u304c\u3042\u308b\u3002\u8a08\u7b97\u91cf\u306f\u3053\u3046\u306a\u308b\u3002<\/p>\n\n\n\n
$O(CL\/M(C\\times(M\/C)\\log (M\/C)+M))=O(CL\\log (M\/C))$<\/p>\n\n\n\n
$C$\u500d\u3088\u308a\u5c11\u3057\u8efd\u3044\u304f\u3089\u3044\u306e\u3088\u3046\u3060\u3002\u3053\u3053\u3067$C=M$\u3068\u3059\u308b\u3068\u666e\u901a\u306b\u3084\u3063\u305f\u3068\u304d\u3068\u7b49\u4fa1\u306b\u306a\u308a2\u4e57\u306e\u30aa\u30fc\u30c0\u30fc\u306b\u306a\u308b\u3002\u3084\u306f\u308a\u9ad8\u901f\u306a\u5fdc\u7b54\u3092\u6c42\u3081\u308b\u307b\u3069\u8ca0\u8377\u306f\u9ad8\u304f\u306a\u308b\u3053\u3068\u304c\u5206\u304b\u308b\u3002<\/p>\n\n\n\n
FFT\u306b\u4f7f\u3046\u30e9\u30a4\u30d6\u30e9\u30ea\u3082\u8abf\u3079\u305f\u306e\u3060\u304c\u3001muFFT\u3068\u3044\u3046\u306e\u304c\u826f\u3055\u3052\u3060\u3063\u305f\u3002MIT\u30e9\u30a4\u30bb\u30f3\u30b9\u3060\u3057\u3002\u3053\u306e\u30e9\u30a4\u30d6\u30e9\u30ea\u306f\u4ee5\u4e0b\u306e\u30d9\u30f3\u30c1\u30de\u30fc\u30af\u304b\u3089\u77e5\u3063\u305f\u3002<\/p>\n\n\n\n