Kiss link:KissFFT有多快

关于Kiss link的问题,在fast kiss中经常遇到, 主题问题:Kiss FFT 在大 O 符号中有多快?

主题问题:Kiss FFT 在大 O 符号中有多快?

3

我很确定快速傅里叶变换的是 θ(n log n)。
如果速度较慢,则不会称为“快速”傅里叶变换。
(而且可能不会更快。)

说到“简单”FFT,这里有一个(只有 2 的幂):

// To get the discrete Fourier _series_, divide by the period
template<class RanInIt, class RanOutIt, class RanScratchIt>
void fft(RanInIt begin, RanInIt end,
    RanOutIt outputs, RanScratchIt scratch /* at least twice as big as output */,
    bool const inverse = false, size_t const stride = 1)
{
    typedef std::iterator_traits<RanInIt>::value_type complex;
    static long double const two_pi = 6.2831853071795864769252867665590057683943L;
    size_t const n = 1 + static_cast<size_t>(std::distance(begin, end) - 1) / stride;
    if ((n & (n - 1)) != 0) { throw std::logic_error("FFTs must be in powers of 2!"); }
    complex const divisor(inverse ? n : 1);
    if (n > 2)
    {
        fft(begin + 0 * stride, end, scratch + 0 * stride, outputs + 0 * stride, false, 2 * stride);
        fft(begin + 1 * stride, end, scratch + 1 * stride, outputs + 1 * stride, false, 2 * stride);
        size_t const n_2 = n / 2;
        for (size_t i = 0; i < n_2; i++)
        {
            using std::polar;
            complex const
                t(polar(1.0L, -two_pi * i / n)),
                s  (*(scratch + (2 * i + 0) * stride)),
                psi(*(scratch + (2 * i + 1) * stride) * t);
            *(outputs + ((i +   0) * stride)) = (s + psi) / divisor;
            *(outputs + ((i + n_2) * stride)) = (s - psi) / divisor;
        }
    }
    else if (n > 0)
    {
        *(outputs + (0 * stride)) = (*begin + *(begin + 1 * stride)) / divisor;
        *(outputs + (1 * stride)) = (*begin - *(begin + 1 * stride)) / divisor;
    }
    if (inverse)
    {
        std::swap_ranges(outputs + 1, outputs + n / 2, std::reverse_iterator<RanOutIt>(outputs + n));
    }
}
template<class RanInIt>
std::vector<typename std::iterator_traits<RanInIt>::value_type>
    fft(RanInIt begin, RanInIt end, bool const inverse = false)
{
    size_t const n = static_cast<size_t>(std::distance(begin, end));
    size_t log2ceil_n = 0;
    for (size_t i = 1; i < n; i *= 2) { log2ceil_n++; }
    std::vector<typename std::iterator_traits<RanInIt>::value_type>
        outputs(static_cast<size_t>(1) << log2ceil_n),
        scratch(2 * outputs.size());
    fft(begin, end, outputs.begin(), scratch.begin(), inverse);
    outputs.resize(n);
    return outputs;
}
template<class Range>
std::vector<typename Range::value_type> fft(Range range, bool const inverse = false)
{ return fft(range.begin(), range.end(), inverse); }
template<class T, size_t N>
std::vector<T> fft(T const (&range)[N], bool const inverse = false)
{ return fft(&range[0], &range[N], inverse); }
0

所有 FFT 实现都具有相同的复杂度,因为它们都是完全相同的算法

存在许多用于计算离散傅里叶变换的算法,但只有一种是“快速傅里叶变换 (FFT)”。

本站系公益性非盈利分享网址,本文来自用户投稿,不代表码文网立场,如若转载,请注明出处

(910)
Unity和unity3d:Unity3D中的动量和惯性
上一篇
经典软件:如何从经典VM分离Azure经典 NSG
下一篇

相关推荐

发表评论

登录 后才能评论

评论列表(64条)