求助复杂度分析
查看原帖
求助复杂度分析
580608
lupengheyyds楼主2025/6/19 19:16

第一篇题解提到了两个递归式以及复杂度，请问为什么是这样。谢谢。

一

g(n,k)=∑D∣kμ2(D)g(⌊nD⌋,D)\def \w#1#2{\left\lfloor\frac{#1}{#2}\right\rfloor} g(n,k)=\sum_{D|k}\mu^2(D)g(\w nD,D)

的复杂度为 O(d(k)n+n23+k)\mathcal O(d(k)\sqrt n+n^{\frac 23}+k)。

二

f(n,m,k)=∑d∣kμ(d)f(⌊md⌋,n,d)\def \w#1#2{\left\lfloor\frac{#1}{#2}\right\rfloor} f(n,m,k)=\sum_{d|k}\mu(d)f(\w md,n,d)

的复杂度为 O(nlog⁡nlog⁡m+n23)\mathcal O(\sqrt n\log n\log m+n^{\frac 23})

2025/6/19 19:16