请教一下杜教筛的时间复杂度分析
  • 板块学术版
  • 楼主BJEA赵子潇
  • 当前回复6
  • 已保存回复6
  • 发布时间2021/1/11 21:19
  • 上次更新2023/11/5 04:54:54
查看原帖
请教一下杜教筛的时间复杂度分析
94193
BJEA赵子潇楼主2021/1/11 21:19

大佬的博客

其他的地方都看懂了,但是无法理解为什么说下一层递归是高阶小量,因而忽略。当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}}),离散的更小一点)

2021/1/11 21:19
加载中...