保存帖子
发现
索引
热门
陶片放逐
关于
杜教筛的复杂度分析，帮忙看看错哪了？
板块
学术版
楼主
AffineRing
当前回复
4
已保存回复
4
发布时间
2020/12/4 14:58
上次更新
2023/11/5 06:44:11
查看原帖
更新帖子
被骇客
银
狼
阻止的越权访问
保存失败
杜教筛的复杂度分析，帮忙看看错哪了？
AffineRing
楼主
2020/12/4 14:58
结合数论分块，单次求和的代价为
n
\sqrt{n}
n
递归求解
F
(
x
)
F(x)
F
(
x
)
时，
x
x
x
可能的取值总共有
n
\sqrt{n}
n
个，即不同的
⌊
n
/
x
⌋
\lfloor n/x\rfloor
⌊
n
/
x
⌋
的个数
每个值只会求解到一次，所以对于每个
x
x
x
，转移的代价都是
x
\sqrt{x}
x
。
所以总复杂度
∑
i
=
1
n
(
i
+
n
/
i
)
\sum_{i=1}^{\sqrt{n}}\left(i+\sqrt{n/i}\right)
i
=
1
∑
n
(
i
+
n
/
i
)
很显然后面的比前面大。因此只考虑后面。
∑
i
=
1
n
n
/
i
=
∫
0
n
n
x
\sum_{i=1}^{\sqrt{n}}\sqrt{n/i}=\int_{0}^{\sqrt{n}}\sqrt{\frac{n}{x}}
i
=
1
∑
n
n
/
i
=
∫
0
n
x
n
并且
∫
n
x
=
n
∫
x
−
1
2
=
2
n
x
\int \sqrt{\frac{n}{x}}=n\int x^{-\frac{1}{2}}=2n\sqrt{x}
∫
x
n
=
n
∫
x
−
2
1
=
2
n
x
然后根据牛顿
−
-
−
莱布尼茨公式
∫
0
n
n
x
=
2
n
n
=
2
n
5
4
\int_{0}^{\sqrt{n}}\sqrt{\frac{n}{x}}=2n\sqrt{\sqrt{n}}=2n^{\frac{5}{4}}
∫
0
n
x
n
=
2
n
n
=
2
n
4
5
？？？？？
错哪了？
2020/12/4 14:58
加载中...
