アルゴリズムの計算量を表現する方法として、記法や記法、記法があります。 それらの定義と違いについてまとめていきます。 定義 何らかのアルゴリズムの計算量が自然数から自然数への関数で表されるとするとき それぞれの定義はこのようになっています $$ O…

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