August 2017
Intermediate to advanced
360 pages
8h 35m
Chinese
Content preview from 算法技术手册（原书第2 版）
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,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
空间树结构
｜
267
空间树结构
10.1 最近邻查询
给定一个二维平面的点集
P
，判断
P
中离目标点
x
的欧几里得距离
最近
的点。注意：点
x
并不一定在
P
中，这与第
5
章中介绍的搜索算法有所不同。这些查询还可以将输入点
集扩展至
n
维。
比较初级的实现方式是探测
P
中的所有点，此算法的时间复杂度是线性
O
(
n
)
。考虑到
已经事先知道
P
的存在，也许我们可以通过某些方法来为
P
中的信息构建一个合理的
数据结构，通过在查询时抛弃大量不必要的点来加快查询的速度。我们可以将平面分成
m
×
m
个固定大小的格子，如图
10-1a
所示
。
P
中的
10
个点（圆圈所示）被放入了
9
个
封闭的格子中。每个格子中的灰色数字代表了落入其中的点的数量。在寻找点
x
（图中
小的黑色正方形）的最近邻时，我们可以先找到装有它的格子。如果格子不为空，我们
就只需要在那些与圆（以
x
为中心且半径为
m*
sqrt
(2)
）
有交集的格子内寻找最近点。
图 10-1：寻找最近邻的格子方法
在这个例子中，目标格子内没有任何点，因此需要检查邻近的三个格子。这种方法较为
低效，在这里并不太适用，因为事实上许多格子都是空的。也就是说，按照这种算法依
然需要搜索多个邻近的格子。在第
5
章中我们看到，二叉搜索树通过排除不可能是解的
点减少了工作量。在本章中，我们引入了
空间树
的思想，将二维平面的进行划分以减少
搜索时间。尽管我们需要一些费用用于将
P
中的所有点组织成高效的数据结构，但是之
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.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.