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.
尾声
：
算法原理
｜
325
尾声：算法
原理
表
12
-
3
：图算法（续）
算法 最好 平均 最差 涉及概念
Dijkstra 算法稠
V
2
+
E
V
2
+
E
V
2
+
E
有向带权图和溢出
密图版本
Floyd-Warshall
V
3
V
3
V
3
动态规划
、
有向带
算法 权图和溢出
Prim 算法 (
V
+
E
)log
V
(
V
+
E
)log
V
(
V
+
E
)log
V
有向带权图
、
二
叉堆
、
优先队列
和贪心
在与复杂的
n
维数据打交道时，需要用更加复杂的递归结构来保存数据。第
10
章介绍
了高级的
空间树
结构，它们可以高效地支持标准的搜索查询以及更加复杂的范围查询。
这些数据结构都经过精心设计，且都扩展自计算机科学里最基础的递归数据结构——
二
叉树
。
12.4 空间换时间
许多算法在计算方面的优化都是通过存储过去的计算结果来实现的。计算图的最小生成
树的
Prim
算法
使用了一个优先队列来存储没有访问过的结点，以此来计算它和初始结
点
s
之间的最短距离。作为算法中的关键一环，我们必须要判断出一个给定结点是否已
经被访问过。由于二叉堆实现的优先队列无法解决这个问题，我们使用了一个单独的布
尔数组来记录每个结点的访问状态。同样在这个算法中，我们还使用了另外一个数组来
保存计算过的距离，以避免在优先队列中进行重复查找。这些额外的存储需要耗费
O
(
n
)
的空间，却保证了算法的高效实现。在大多数情况下，使用
O
(
n
)
的空间无关紧要。
有时还可以通过缓存整个计算过程来避免重复计算。在第
6
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.