c++ - ループの下で FFT 乗算の Big-O 表記を見つける方法

Question

FFT 乗算の Big-O 表記は O(nlogn) です。以下のアルゴリズムに示されているループ下での FFT 乗算の Big-O 表記は何ですか? コードはmatlabで提供され、FFTmultiは2つの多項式のFFT乗算の関数です

rG=1;
rN=1;
AreaFunc=[1 2 5 2 3 6 7 2 4 5 6];

N=length(AreaFunc);

for i=1:(N-1)
    ref_coeff(i) = (AreaFunc(i+1) - AreaFunc(i)) / (AreaFunc(i+1) + AreaFunc(i));
end

ref_coeff=[ref_coeff rN];
G = (1 + rG) / 2;
A0 = [1]; B0 = [-rG];

for i = 1 : length(ref_coeff)
    G = G * (1 + ref_coeff(i));
    A1 = [-ref_coeff(i) 0]; B1 = [1 0];
    An = [0 A0] + FFTmulti(A1,B0);
    Bn = [0 -ref_coeff(i)*A0] + FFTmulti(B1,B0);
    A0=An;
    B0=Bn;
end

A0 =fliplr(A0);
num = zeros(1, (floor(N/2)));
num = [num G];

Answer 1

FFT の複雑さ (最もよく知られている最適化アルゴリズムの場合) は N*log2(N) です。

N のループ内で呼び出すと、N^2 log2(N) になります。