所以分治里面加sort到底会不会多log(极限数据)

P1429 平面最近点对（加强版）

zzzyyyyhhhhh @ 2024-05-27 22:08:57

rt（极限数据）

看到两篇题解说不用归并排序的话会多一个log，但有人说不会，蒟蒻不会计算复杂度，求问dalao

by ScaredQiu @ 2024-05-27 22:18:23

分治里边用 sort的复杂度是 O(n \log^2 n) 的。

by ScaredQiu @ 2024-05-27 22:18:40

@zzzyyyyhhhhh

by WrongAnswer_90 @ 2024-05-27 22:32:03

T(n)=2T(n/2)+O(n\log n)

主定理算一下是 \mathcal O(n\log^2 n) 的

|