V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
letianqiu
V2EX  ›  程序员

一道 FFT 相关的题

  •  
  •   letianqiu · 2018-04-13 18:06:24 +08:00 · 3025 次点击
    这是一个创建于 2398 天前的主题,其中的信息可能已经有所发展或是发生改变。
    K 个多项式,这 K 个多项式最高次数的和是 S。如何在 O(SlogSlogK)内求出这 K 个多项式的乘积。
    O(KSlogS)很容易,只需要对每个多项式做 FFT, O(SlogS),然后依次逐点相乘,最后 IFFT。总的复杂度就是 O(KSlogS)。但是如何把 K 变成 logK 就想不到了,尝试两两相乘,但是复杂度并不能降低。
    第 1 条附言  ·  2018-04-13 21:20:02 +08:00

    fft.png

    2 条回复    2018-04-13 22:03:31 +08:00
    wodesuck
        1
    wodesuck  
       2018-04-13 21:59:15 +08:00   ❤️ 2
    两两相乘复杂度是 O(SlogSlogK)的。
    两个 degree 为 a 和 b 的多项式相乘,是 O((a+b)log(a+b))。考虑做第一次两两相乘,P1 乘 P2,P3 乘 P4,P5 乘 P6...,复杂度就是 O( (d1+d2)log(d1+d2) + (d3+d4)log(d3+d4) + ...) < O((d1+d2+d3+...)logS) = O(SlogS)。乘完后 degree 和不变,下一次两两相乘的复杂度还是 O(SlogS),一共要做 logK 趟。
    zjuturtle
        2
    zjuturtle  
       2018-04-13 22:03:31 +08:00
    可以参考一下我的博客
    https://zjuturtle.com/2017/12/26/fft/
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3400 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 11:05 · PVG 19:05 · LAX 03:05 · JFK 06:05
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.