背景
高速フーリエ変換の Cooley-Tukey のアルゴリズムを使うと、乗算回数が$N^2$から $N \log_2 N$ となる事実はしっていても、なんとなく $\log_2 N$ がでてくる理由がピンとこない人向け。Cooley-Tukey のアルゴリズムの解説は割愛するので、参考ページや他によいページがあるので、忘れた方は復習をしてください。
直感的な説明
まずは数式を日本語化して考えてみよう。計算回数が$\log_2 N$に比例するという部分は、
計算回数 = \log_2 N = \log_2 データ数
という意味となる、これを指数関数で書き換えてみる。
N = データ数 = 2^{計算回数}
もう一歩具体化を進めて、データ数が２倍になった場合を考えると、
2N = 2 \times データ数 = 2^{計算回数+1}
となる。
つまり、データ数が２倍になったときに、計算回数が１しか増えない状況の場合は、計算回数が $\log_2 N$に比例する。アルゴリズムとの対応ではこの方が直感的な気がする(当然だが、、$\log_2 2N = 1 + \log_2 N$ なので計算回数が１増える、とも考えられる。あくまで感覚的なお話です。)
誤解のないように、トータルのFFTの場合を補足すると、計算回数は$\log_2 N$ではなくて、$N \log_2 N$に比例するので、データ数が２倍になったときに、新しいデータがN個だけ加わった分の長波長成分の計算は必要になる。
フーリエ変換は周期性のある基底で展開するので、データが増えても高周波成分の位相の計算は新しくする必要がない。データが増えることで必要となる長い波長成分(低周波数成分)だけの計算で済む。フーリエ変換は対称性を持つため、それを利用した効率的な計算方法が可能になる。