求助 cdq 分治的时间复杂度计算
查看原帖
求助 cdq 分治的时间复杂度计算
598026
hzlqwq楼主2024/3/27 23:02

请问为什么 cdq 分治解决三维偏序问题的时间复杂度是 O(nlog⁡2n)O(n\log^2n) 呢?有详细解释嘛?

如果式子是 T(n)=2T(n2)+O(nlog⁡n)T(n)=2T(\frac{n}{2})+O(n\log n) 的话,那么根据主定理,由于 nlog⁡22<nlog⁡nn^{\log_2 2}<n\log n,T(n)T(n) 不应该等于 O(nlog⁡n)O(n\log n) 嘛?

我看 wiki 上写的式子是 T(n)=T(⌊n2⌋)+T(⌈n2⌉)+O(nlog⁡n)T(n)=T(\lfloor\frac{n}{2}\rfloor)+T(\lceil\frac{n}{2}\rceil)+O(n\log n),是上下取整的问题嘛?

2024/3/27 23:02
加载中...