好像直接套主定理就行了
by ddwqwq @ 2019-01-22 22:19:10
@[杜岱玮](/space/show?uid=64366) 不会用主定理呀、
by 星小雨 @ 2019-01-22 22:22:22
@[星小雨](/space/show?uid=20435) 就是分治啊。。递归的每一层时间复杂度是$\Theta(n)$的，会递归$\log n$层，所以时间复杂度是$\Theta(n\log n)$。。
应该就是这样
by NaCly_Fish @ 2019-01-22 22:24:06
@[NaCly_Fish](/space/show?uid=115864) 可是我每层都要跑FFT啊。。
by 星小雨 @ 2019-01-22 22:31:48
@[星小雨](/space/show?uid=20435) 每层的循环是线性的啊
by NaCly_Fish @ 2019-01-22 22:32:46
~~我怎么觉得您们说的好像不是同一个东西~~
by xenonex @ 2019-01-22 22:37:57
@[NaCly_Fish](/space/show?uid=115864) 楼主说的是**分治**FFT。确切的说，是分治“套”FFT。
递归式为$$\text{T}(n)=\text{T}(n/2)+\text{O}(n\text{lg}n)$$ 解得$\text{T}(n)=\text{O}(n\text{lg}n)$
by ddwqwq @ 2019-01-23 00:09:29
不对，刚才弄错了，分治FFT是递归两次，那应该是两个log？这至少是个上界，我不知道如何证明它的确界。这玩意好像套不了主定理。
by ddwqwq @ 2019-01-23 00:32:55