请问为什么 cdq 分治解决三维偏序问题的时间复杂度是 O(nlog2n)O(n\log^2n)O(nlog2n) 呢?有详细解释嘛?
如果式子是 T(n)=2T(n2)+O(nlogn)T(n)=2T(\frac{n}{2})+O(n\log n)T(n)=2T(2n)+O(nlogn) 的话,那么根据主定理,由于 nlog22<nlognn^{\log_2 2}<n\log nnlog22<nlogn,T(n)T(n)T(n) 不应该等于 O(nlogn)O(n\log n)O(nlogn) 嘛?
我看 wiki 上写的式子是 T(n)=T(⌊n2⌋)+T(⌈n2⌉)+O(nlogn)T(n)=T(\lfloor\frac{n}{2}\rfloor)+T(\lceil\frac{n}{2}\rceil)+O(n\log n)T(n)=T(⌊2n⌋)+T(⌈2n⌉)+O(nlogn),是上下取整的问题嘛?