首页 » 算法技术手册 » 算法技术手册全文在线阅读

《算法技术手册》分析

关灯直达底部

如果k d树初始是平衡的,那么每一层的切分线正好穿过此层的中点。我们能够在O(log n)的时间内找到目标点区域。但是,这个算法有可能会调用两个查找:一个是查找左子树,一个是查找右子树。如果这种情况频繁地出现,算法的性能会退化到O(n),所以值得我们分析这种情况发生的频率。当从目标点到节点的垂直距离dp小于已知最小距离时,我们可能需要执行多个调用。随着维度的增长,可能会有更多的点满足这个条件。表9-6是这种情况发生几率的经验性总结。我们在单位正方形中生成n个随机二维点,n从4~131 072,在这些点上构建一棵平衡的kd树。我们会有50个查询,表9-6记录了两个递归调用和单个递归调用发生的平均次数。

我们可以看到,在随机生成的二维数据上,产生两个调用的次数是0.3*log(n),但是在十维上,这个数目会升到342*log(n)(1000倍左右的提升)。我们可以观察到,这个估计值大约是O(log n)。但是当d增长到“足够接近”n时,会发生什么呢?图9-22的结果告诉我们,随着d的增长,两个调用发生的次数逐渐逼近n/2。事实上,d增长时,单次调用的次数遵从正态分布,其中值趋近于log(n),两种递归调用最终恰好是各占一半。这个结论对与性能的影响就是使得查询在d增长的情况下,性能逼近log(n)。在这种极端情况下,使用kd树,性能不会好于O(n)。

图 9-22 随着n和d增长,两个递归调用的次数

算法在某些特定的输入数据上性能退化非常严重。例如,我们将表9-6的输入点改成在一个半径大于1的圆内,但是查询的点还是在单位正方形中。当n=131 072时,单个递归调用的数量跳到235.8个,而两次递归调用的数量会增加到932.78个。因此最邻近点算法的性能会退化到最坏的O(n)。

我们也可以对比一下基于kd树的最邻近点算法和穷举算法的性能。我们有这样一个例子,4096个点和128个查询,那么维度d从多大开始,kd树的性能会差于最原始的穷举算法呢?我们执行了100次实验,抛弃最好和最坏的结果,取剩余98次的平均值。结果如图9-23所示,维度从10开始,原始的穷举算法的性能就开始占优。当n增加到131 072个,原始穷举算法的性能在d=12时开始占优,所以拐点出现的位置和n、d以及输入点的分布情况相关。我们不会分析在这个拐点上,构建kd树的开销是多少,因为这个开销都被分摊到了每次查询上。

图 9-23 比较kd树和穷举实现

图9-23的结果证实了随着维度的增加,使用kd树获得的性能改进越来越少。等式中主要的驱动因素不是构建kd树的开销,而是将要插入kd树中的点的个数。在大规模数据集合上,节省的开销是显而易见的。另外一个影响性能的因素是维度d,计算两个d维点的欧几里德距离是O(d)的操作,随着d增加,每次计算需要更多的时间。