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.
160
｜
第
6
章
6.9.2 图分析
在应用本章的算法时，是否使用邻接表还是邻接矩阵本质上取决于图是否稀疏。算法的
性能按照图中的顶点数
V
以及
边数
E
来计算
。与其他算法书一样，我们简化了性能公式，
无论在最好、最坏还是平均情况下，都使用
V
、
E
的大
O
记法来表示性能。
O
(
V
)
表示需
要直接正比于图中顶点数的计算步数。不仅如此，图中边的密度也必须考虑。在稀疏图中，
O
(
E
)
约等于
O
(
V
)
，然而在稠密图中，它更接近
O
(
V
2
)
。
我们会看到，某些算法的性能取决于图的结构，一种算法可能需要的执行时间是
O
((
V
+
E
)*
log V
)
，而另外一种可能需要
O
(
V
2
+
E
)
。那么，哪种算法那更加高效呢？表
6-4
显示
这个答案取决于图
G
是稀疏还是稠密。对于稀疏图来说，
O
((
V
+
E
)*log
V
)
更加高效；
对于稠密图而言，
O
(
V
2
+
E)
则更加快速。标记为“均衡图”的条目说明这些图的期望性
能在稀疏图和稠密图上都是相同的，都是
O
(
V
2
)
，在这些图上，边的数目约等于
O
(
V
2
/
log
V
)
。
表
6
-
4
：两种衍生算法的性能比较
图类型
0
((
V
+
E
)*log
V
) 比较关系
0
(
V
2
+
E
)
稀疏图
：
O
(
V
log
V
) 小于
O
(
V
2
)
|
E
| 是
O
(
V
)
均衡图
：
O
(
V
2
+ V*
log
V
)=
O
(
V
2
) 等于
O
(
V
2
+
V
2
/
log
V
)=
O
(
V
2
)
|
E
| 为
O
(
V
2
/
log
V
)
稠密图
：
O
(
V
2
log
V
) 大于
O
(
V
2
)
|
E
| 为
O
(
V
2
)
6.10 参考文献
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.