高速フーリエ変換 - Wikipedia

高速フーリエ変換（こうそくフーリエへんかん、英: fast Fourier transform, FFT）は、離散フーリエ変換（英: discrete Fourier transform, DFT）を計算機上で高速に計算するアルゴリズムである。高速フーリエ変換の逆変換を逆高速フーリエ変換（英: inverse fast Fourier transform, IFFT）と呼ぶ。 概要[編集] 複素関数 f(x) の離散フーリエ変換である複素関数 F(t) は以下で定義される。 このとき、{x = 0, 1, 2, ..., N − 1} を標本点と言う。 これを直接計算したときの時間計算量は、ランダウの記号を用いて表現すると O(N2) である。 高速フーリエ変換は、この結果を、次数Nが2の累乗のときに O(N log N) の計算量で得るアルゴリズムである。より一般的には、次数が N =

[ksd6700]

.

[haru-s]

FFT

[kazumeat]

@mitukiii 高速フーリエ変換のことですか？

[underthemoon]

Fast Fourier Transform ; FFT "離散フーリエ変換 (Discrete Fourier Transform, DFT) を計算機上で高速に計算するアルゴリズム"