K-D树 专题训练 数据结构

K-D树 专题训练

K-D树,主要可以解决一些在多维空间上带有限制或者查询临近元素的问题。主要思想就是将数据点划分成许多块(二维情况下就是矩形),然后利用估值函数来减小查询涉及到的范围。 这玩意的复杂度不像其他数据结构那么稳定,一般来说,复杂度都是O(logn)级别的,但是查询操作最坏能被卡到O(n^(1-1/k))的···