c++ - 如何在循环下找到 FFT 乘法的 Big-O 表示法

Question

FFT 乘法的大 O 表示法是 O(nlogn)。如下算法中给出的循环下 FFT 乘法的 Big-O 表示法是什么？代码在 matlab 中给出，FFTmulti 是两个多项式的 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)。