基于KD树（平衡二叉树）的1-NN搜索时间复杂度范围是多少？

假设数据集中包含N个点，使用平衡二叉树结构的KD树进行1-NN（最近邻）搜索的时间复杂度处于什么范围？

选项：

• A) O(N²) - O(N³)
• B) O(log N) - O(N)
• C) O(N logN) - O(N²)
• D) 以上都不是

答案与解析 #

正确选项为 B。

• 最优场景下，当数据分布均匀时，KD树的1-NN搜索只需遍历树的一条路径并进行少量回溯，时间复杂度为 O(log N)；
• 最坏场景下，若数据点近似线性分布（比如所有点落在一条直线上），KD树会退化为线性结构，此时搜索需要遍历所有点，时间复杂度为 O(N)。

内容的提问来源于stack exchange，提问作者deilsdironan