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.
250
｜
第
9
章
线段扫描算法
的性能是
O
((
n + k
)log
n
)
，因为它会在扫描点不断处理时对有效线段进行
重排序。如果这一步需要的时间多于
O
(log
s
)
（
s
是状态中的线段数目），那么整体性
能将会退化到
O
(
n
2
)
。例如，如果线段状态采用双向链表（一种能够快速找到前驱和后继
线段的数据结构）来存储线段，那么由于需要在表中找到正确的插入位置，插入操作将
会增加到
O
(
s
)
。随着线段集
s
的增长，性能退化将会变得很明显。
类似地，事件队列需要能够高效地查询某个事件点是否已经在队列中。使用基于堆的优
先队列实现（即
java.util.PriorityQueue
）同样会使得算法退化到
O
(
n
2
)
。我们不希
望口口声声说是
O
(
n
log
n
)
的算法，最后实现的却是
O
(
n
2
)
的性能！
9.5.4 算法分析
线段扫描算法
会将多达
2
*n
个端点插入事件队列中。这个队列能够支持在
O
(log
q
)
的时
间内（
q
是队列中元素个数）完成如下操作：
min
从队列中删除最小的元素。
insert(e)
将元素
e
插入有序队列中的适当位置。
member(e)
判断给定的元素
e
是否已经在队列中。通用型优先队列并不需要严格支持这类操作。
唯一点出现在事件队列中——换言之，如果待插入的事件点已经存在，那么它的信息会
被加至已存在的事件点的信息中。因此，当图
9-7
的点最初被插入优先队列时，优先队
列仅包含
8
个事件点。
线段扫描算法
从上到下进行扫描，然后通过以适当的顺序添加或删除线段，进而更新线
段的状态。在图
9-7
中，在按照从左到右的顺序对事件点进行处理后，有序线段的状态 ...
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.