如何在循環下查找FFT乘法的Big-O符號

Question

FFT乘法的Big-O符號是O（nlogn）。在下面的算法中給出的循環下的FFT乘法的Big-O符號是什麼？該代碼在MATLAB中給出和FFTmulti是兩個多項式

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的複雜性 - 對於最好的已知優化算法的用於FFT乘法函數 - 是N * LOG2（N）。

如果你在一個N循環內調用它，將會是N^2 log2（N）。