問題 No.1575
離散フーリエ変換（DFT）の計算量を削減するアルゴリズムである高速フーリエ変換（FFT）を用いて、データ数 N = 1024 の信号を処理する場合、通常の直接的なDFTと比較して、計算のおおよそのオーダー（演算回数）は何分の1に削減されるか。最も適切なものを選択せよ。
【正解の解説】
約 102 分の 1
これは辞書を引くときに、1ページずつめくる全探索（DFT）から、真ん中を開いて半分ずつ絞り込む二分探索（FFT）に変えるようなものです。データ数がN=1024の場合、N^2は約100万回ですが、N log2 Nは約1万回となり、手探りで探す苦労がスマートな手順で約102分の1へと劇的にラクになります。
スポンサーリンク
【その他の選択肢の解説】
約 512 分の 1
初学者が「半分に効率化するから512分の1だろう」と勘違いしやすいように作られた罠の選択肢です。計算量は足し算や引き算のように単純な比例ではなく、Nの2乗とN log2 Nという累乗と対数の関係で劇的に差が開くため、このように直感とは大きく異なる数値になります。
約 20.5 分の 1
公式であるN^2とN log2 Nの比率を計算する際、底を2ではなく10で計算してしまったり、指数部分の処理を誤るとこのような中途半端な値が出てきます。試験ではこうした計算ミスの結果をあえて選択肢に混ぜてくるため、オーダーの本質的な意味を理解しているかが問われます。
約 10 分の 1
「1024だから10に関する数字だろう」という表面的な連想を誘うためのひっかけ選択肢です。FFTの計算量はデータの大きさそのものではなく、それが2の何乗であるかというビット数（今回はlog2(1024)=10）が深く関わってくるため、このような安易な数字の連想で選ぶと見事に罠にハマってしまいます。