F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
大视野在线测评-欢迎您
[ New Thread ]
Problem 2648 >> 强烈要求加强数据!
dogther @ 2016-07-10 16:09:53
[ Quote ] [ Edit ] [ Delete ] 1#
kd树暴力插入的复杂度显然是n^2的!必须要用替罪羊树的思想重构才能保证复杂度。为什么网上的题解一个个都是暴力插入的啊?!
以下这组数据就可以卡掉:
1 500000
1 0
1 1 1
1 1 2
1 1 3
......
1 1 499999
2 2 1
dogther @ 2016-07-10 17:16:58
[ Quote ] [ Edit ] [ Delete ] 2#
或者至少把要插入的点离个线提前建好啊...
Recursion @ 2016-07-10 17:41:48
[ Quote ] [ Edit ] [ Delete ] 3#
遗憾的是,就算你加了重构,询问依然可以卡到nm
nzhtl1477 @ 2016-07-11 07:45:23
[ Quote ] [ Edit ] [ Delete ] 4#
Orz千古神犇dogther
dogther @ 2016-07-11 16:50:40
[ Quote ] [ Edit ] [ Delete ] 5#
所以怎么卡?是因为kd树本身复杂度的问题吗?
lavendir @ 2016-07-11 23:21:28
[ Quote ] [ Edit ] [ Delete ] 6#
加强的数据,可发到Lydsy2012@163.com
Recursion @ 2016-07-13 10:14:01
[ Quote ] [ Edit ] [ Delete ] 7#
kdtree询问最近点本来就是O(n)一次啊...
dogther @ 2016-07-14 14:06:39
[ Quote ] [ Edit ] [ Delete ] 8#
但我记得(二维)kd树复杂度不是O(sqrt(n))吗?还是说只有查最近点时候会退化,而比如说询问矩形内点的个数什么的不会退化?
Recursion @ 2016-07-14 16:46:16
[ Quote ] [ Edit ] [ Delete ] 9#
剖矩形是O(\sqrt n)的,查找最近点本质就是暴力剪枝,显然是O(n)的。
dogther @ 2016-07-14 20:34:18
[ Quote ] [ Edit ] [ Delete ] 10#
原来是这样,网上基本上没有关于kd树时间复杂度的说明,受教了!
nzhtl1477 @ 2016-07-15 00:10:44
[ Quote ] [ Edit ] [ Delete ] 11#
%%%
DZYO @ 2017-09-30 11:14:43
[ Quote ] [ Edit ] [ Delete ] 12#
能不能写一个替罪羊树套进去,我写的跑了10s。
PhoenixEclipse @ 2019-02-26 18:59:22
[ Quote ] [ Edit ] [ Delete ] 13#
还是别加强数据了吧……大家都知道KDTree复杂度不对,但是这题不就是用来给我这样刚学KDTree的萌新练手的么qwq
[Top] [Previous Page] [Next Page]

HOME Back