Skip to Main Content
算法技术手册(原书第2 版)
book

算法技术手册(原书第2 版)

by George T.Heineman, Gary Pollice, Stanley Selkow
August 2017
Intermediate to advanced content levelIntermediate to advanced
360 pages
8h 35m
Chinese
China Machine Press
Content preview from 算法技术手册(原书第2 版)
276
10
近的点。因为
k-d
树的矩形区域是基于输入点集合创建的,因此这类检查是非常必要的。
在一棵不平衡的
k-d
树中,这种检查可能会达到
O
(
n
)
的总
费用,因此正确处理输入集合
至关重要。
示例解决方案有两个方面的性能提升。首先,对比都是发生在“原始的
raw
)”
double
型数组之间,每个数组均代表了一个点。其次,
DimensionalNode
中的
shorter
方法被
用于确定两个
d
维点之间的距离是否小于当前计算出的最短距离。该方法在部分计算出
的欧几里得距离超过当前最小值时会立即退出。
假定初始的
k
-
d
树是平衡树,那么搜索在递归调用的过程中可以很方便地舍去树中半数
的点。虽然有的时候两次递归调用是必的,但这只发生在计算出的最短距离刚好大于
穿过结点的切分线时。在这种情况下,我们需要继续搜索切分线两边的区域来找出最近
的点。
10.5.4 算法分析
k
-
d
树最初被构建为平衡
k
-
d
树,每层的切分线源自该层剩余点的中位元素。找到目标
查询的父结点需要
O
(log
n
)
的时间,这可以通过假想点被插入
k
-
d
树中时遍历而得。但是,
算法可能会需要进行两次递归调用:一次用于遍历上方的子结点;另一次用于遍历下
方的子结点
如果两次递归的调用过于频繁,算法的性能会退化到
O
(
n
)
,因此有必要了解这种情况
发生的频率。只有当目标点到树结点中的点的垂直距离
dp
小于计算出的最小距离时,
多次调用才会发生。随着维度的增加,将会有越来越多的点满足这些条件。
10-1
给出了一些实证说明这种情况发生的频率。表中的平衡
k
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

机器学习实战:基于Scikit-Learn、Keras 和TensorFlow (原书第2 版)

机器学习实战:基于Scikit-Learn、Keras 和TensorFlow (原书第2 版)

Aurélien Géron
Go语言编程

Go语言编程

威廉·肯尼迪
C++语言导学(原书第2版)

C++语言导学(原书第2版)

本贾尼 斯特劳斯特鲁普

Publisher Resources

ISBN: 9787111562221