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

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

g(n,k)=Dkμ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)=dkμ(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(nlognlogm+n23)\mathcal O(\sqrt n\log n\log m+n^{\frac 23})

2025/6/19 19:16
加载中...