知识卡片

普通读书笔记卡 · 3693.c.1.b

FFT复杂度来自双递归线性合并

理解等级:中级

基于偶奇拆分的FFT每层做两个n/2规模DFT,并用Θ(n)次合并操作;递推T(n)=2T(n/2)+Θ(n),得到Θ(n lg n)。

关键节省是共享单位根采样点,并非逐点独立套用霍纳法。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第30章 多项式与快速傅里叶变换 · 查看原书依据

      The recurrence for the running time is therefore T(n) = 2T(n/2) + Θ(n) = Θ(n lg n), by case 2 of the master theorem (Theorem 4.1). Thus the FFT can evaluate a polynomial of degree-bound n at the complex nth roots of unity in Θ(n lg n) time. Interpolation at the complex roots of unity The polynomial multiplication scheme entails

    参考来源

    - 位置:《算法导论(第4版)》第30章《多项式与快速傅里叶变换》(OEBPS/chapter030.xhtml,文本字符[20000,25000))。 - 结论依据:原文定义单位根、DFT、FFT递归、逆变换与电路;相关公式和图已核对。 - 原始内容:The recurrence for the running time is therefore T ( n ) = 2 T ( n /2) + Θ( n ) = Θ( n lg n ), by case 2 of the master theorem (Theorem 4.1). Thus the FFT can evaluate a polynomial of degree-bound n at the complex n th roots of unity in Θ( n lg n ) time. Interpolation at the complex roots of unity The polynomial multiplication scheme entails