高速フーリエ変換とは、離散フーリエ変換を高速に行うアルゴリズムです。 具体的にどのくらい高速なのか気になったので解析してみます。 まず、離散フーリエ変換について 要素数の入力ベクトルを、同じく出力の周波数ベクトルをとすると、離散フーリエ変換は…