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.
328
｜
第
12
章
数计算结果和
凸包扫描
的结果有着略微的不同（尽管差别非常小）。难道这只是偶然吗？
不是。我们也注意到
线段扫描算法
所产生的结果和
穷举相交算法
的结果也有些许不同。
那么，到底哪个算法的结果才是“正确”的呢？答案并没有那么简单，因为用到了浮
点数，我们需要找到一种统一的方式进行比较。具体来说，我们（有点）任意定义
FloatingPoint.epsilon
作为阈值，如果低于该值，就无法判断两个浮点数是否完全相等。
当计算出的结果值接近阈值时（设定为
10
-9
），通常会有一些无法预料的行为发生。当然，
即使不用阈值也不能完全解决这个问题。最终，我们决定使用统计的方法验证算法结果，
而不是去对比所有案例的绝对结果和预期结果。
表
12-7
总结了第
9
章介绍的算法。这些算法在二维几何结构上执行浮点数运算有着同样
的问题。
表
12
-
7
：计算几何
算法 最好 平均 最差 涉及概念
凸包扫描
n n
log
n n
log
n
贪心
线段扫描 (
n
+
k
)log
n
(
n
+
k
)log
n
n
2
优先队列和二叉树
Voronoi 图
n log n n
log
n n
log
n
线段扫描
、
优先队列和二叉树
12.8 在可能的情况下接受近似解
在许多情况下，近似解是可以接受的，如果它的计算速度要比精确解更快，并且它与正
确结果的误差也是已知的。
无界背包问题
就提供了这样的场景，近似解不会比
50%
的
实际解更差。这些近似解可以使用一些随机方法来计算实际解的估值，就像求解
N
皇后
问题解法数量的示例一样。如果 ...
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.