dwjshift's Blog

关于KD tree查询最近点的复杂度

| Comments

不是!不是!不是

很久以前就听说KD tree能做到根号复杂度查询(二维)最近点。前两天去学了KD tree才发现不过是剪了下枝,看起来复杂度很不靠谱啊?
找了很久都没有找到有人证明。基本上都是说“据说是根号”“某神犇跟我说是根号”之类的
自己yy了几幅图发现似乎挺容易就能卡到。跑去某群确认了一下,确实复杂度是不靠谱的。
要卡的话直接放一堆点在圆周上,询问圆心就行了。


竟然无言以对。

Comments

comments powered by Disqus