確率から画像処理まで、離散畳み込みと高速フーリエ変換(FFT) 激ムズ数え上げパズルと驚きの解法 https://youtu.be/FR6_JK5thCY フーリエ変換の解説動画 https://youtu.be/fGos3wrKeHY 【注釈】 整数のかけ算のアルゴリズムについて、FFTの"straightforward"な適用はO(N * log(n) log(log(n)) )の実行時間になる。log(log(n))の項は小さいが、2019年になってHarvey and van der Hoevenがこの項を取り除くアルゴリズムを発見した。また、O(N^2)を、必要な計算量がN^2と共に大きくなると表現したが、厳密にはこれはTheta(N^2)が意味するところである。 O(N^2)は計算量が高々N^2の定数倍になるという意味で、特に、実行時間がN^2項を持たないが有界であるアル