求阶乘复杂度最低的算法

P1591 阶乘数码

密期望 @ 2019-08-21 13:03:24

目前我已知分治FFT（NTT）可以做到O(nlog^2n)。想请教一下有没有更快的算法。

by 密期望 @ 2019-08-21 14:07:19

@WAutomaton

\Pi_{i=l}^{r}i=(\Pi_{i=l}^{mid}i)*(\Pi_{i=mid+1}^{r}i)

分治会递归O(logn)层，每层复杂度O(nlogn)，总复杂度O(nlog^2n)。

我是这么瞎推的，不知道对不对。

by WAutomaton @ 2019-08-21 14:27:13

@密期望我推出的结果是：分治返回的结果的位数是O(n \log n)的，所以单次FFT复杂度为 O((n \log n)\log (n \log n) ) 即 O(n \log ^2 n \log \log n) 的。难道是我推出的上界太松了？

by 小菜鸟 @ 2019-08-21 14:29:28

被大佬叫dalao有点害怕QwQ

by 密期望 @ 2019-08-22 22:54:56

@WAutomaton

高精位数应该是nlgn，lgn一般忽略掉吧，就像\alpha(n)一般被忽略掉，看做常数一样。这里不严谨是我的锅。

还有

O(log(nlgn))=O(logn+loglgn)=O(logn)!=O((logn)*(loglgn))

所以单次FFT复杂度应该为O(n(logn)(lgn))

约为O(nlogn)。

所以总的复杂度应该是O(n(log^2n)(lgn))

约为O(nlog^2n)。

我们有一个log的差距就在lgn上。

by NULL0x7f @ 2019-09-11 12:32:54

@密期望

不是，你喊我也不会啊

话说你这是死灰复燃了？

by impuk @ 2020-01-04 17:35:23

常数卡一下logn不就没了？（说的简单）光速逃

by jijidawang @ 2020-03-03 14:41:16

@密期望

不是 \mathcal{O}(\sqrt{n}\log n) 的吗

上一页 |