这个...主定理告诉我们应该是$O(nlogn)$
或者考虑每层复杂度$O(n)$,一共才$logn$层.
~~sro scb orz~~
by 硫代硫酸钠 @ 2018-05-08 12:38:27
每一次遍历n个点,由于点分治的性质,每次从重心往下走的时候,子树大小必然小于等于之前的一般,最多logn层,所以是nlogn
by moye到碗里来 @ 2018-05-08 13:02:44
@[suncongbo](/space/show?uid=23613)
by moye到碗里来 @ 2018-05-08 13:03:24
@[硫代硫酸钠](/space/show?uid=44273)
@[moye到碗里来](/space/show?uid=52576)
好吧,谢谢。。
by suncongbo @ 2018-05-11 22:39:28
### n^2 log(n)啊
by 人殇物已非 @ 2018-06-14 15:35:07
# n*log^2(n)
这才是对的。。
by 人殇物已非 @ 2018-06-14 15:38:49