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.
324
｜
第
12
章
要注意的是，动态规划虽然也是将问题分解成较小的问题，但是其总体性能往往是
O
(
n
2
)
或者
O
(
n
3
)
，这是因为这些较小的问题通常只比原问题的规模小
1
而不是一半。
表
12-2
比较了第
5
章讨论过的查找算法。这些算法采用了不同的方法回答了最基本的关
于元素对应集合关系的问题。在分析它们的性能时，我们采用了一些技巧来
均摊
操作的
费用，从而能够精确地描述随机搜索查询的平均性能。
表
12
-
2
：查找算法
算法 最好 平均 最差 涉及概念
AV L 二叉搜索树 1 log
n
log
n
二叉树和平衡树
顺序搜索 1
n n
穷举
二叉搜索 1 log
n
log
n
分治
布隆过滤器
k k k
误报率
散列搜索 1 1
n
散列
二叉搜索树 1 log
n n
二叉搜索
12.3 选择正确的数据结构
著名算法设计者
Robert Tarjan
曾经引用过这样一句话：“如果使用正确的数据结构，任
何问题都能够在
O
(
n
log
n
)
的时间内解决”。许多算法需要使用优先队列来存储中间过
程或者指示下一步运算。实现优先队列最常见的方法要数二叉堆了，它能够在
O
(log
n
)
的时间内从优先队列中将最低优先级的元素移除。然而，二叉堆却不能判定是否包含某
个特定的元素。我们在讨论
线段扫描
（第
9
章）时提到过这一点，该算法之所以可以达
到
O
(
n
log
n
)
的性能，是因为它使用了增广二叉树来实现优先队列，它能够保证在移除
最小元素能够达到
O
(log
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.