社区讨论

请教一下杜教筛的时间复杂度分析

学术版参与者 4已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@locqks6e
此快照首次捕获于
2023/10/30 18:07
2 年前
此快照最后确认于
2023/11/05 04:54
2 年前
查看原帖
其他的地方都看懂了,但是无法理解为什么说下一层递归是高阶小量,因而忽略。当i==2,3...的时候n2\frac{n}{2}n3\frac{n}{3}递归下去也挺大的啊。
这是否意味着真正的时间复杂度有可能比O(n23)O(n^{\frac{2}{3}})大。(不过这应该不太会,因为把离散的求和放缩到连续的求和上界才是O(n23)O(n^{\frac{2}{3}}),离散的更小一点)

回复

6 条回复,欢迎继续交流。

正在加载回复...