复杂性思考：复杂性科学和计算模型（原书第2 版）

图

｜

29

因此，这个函数的增长级数是 O(

n

+

m

)，我们可以说，无论

n

和

m

哪个更大，

运行时间与

n

或

m

成正比。

如果知道

n

和

m

之间的关系，我们可以简化这个表达式。例如，在一个完全

图中，边的数目是

n

(

n

–1)/2，在

O

(

n

2

) 中。对于一个完全图，reachable_

nodes 是

n

的二次函数。

2.9 练习

本章的代码在 chap02.ipynb 中，它是本书代码库中的 Jupyter 笔记。有关

使用此代码的更多信息，请参阅前言中的“使用代码”。

练习 2-1

启动 chap02.ipynb 并运行代码。你可能想在笔记本上做一些简单的

练习。

练习 2-2

在 2.8 节中，我们分析了 reachable_nodes 的性能，并将其归类为

O(

n

+

m

)，其中

n

为节点数，

m

为边数。请继续分析，is_conected 的

增长级数是什么？

def is_connected(G):

start = list(G)[0]

reachable = reachable_nodes(G, start)

return len(reachable) == len(G)

练习 2-3

在我的 reachable_nodes 实现中，你可能会为将所有相邻节点添加到

栈而没有检查它们是否已经在集合 seen 中而感到困扰。重新编写一个函

数，在将相邻节点添加到栈之前检查它们是否已经存在于栈中。这种优

化会改变增长级数吗？这会使函数运行得更快吗？

练习 2-4

实际上有两种 ER 图。本章生成了其中一种，G(

n

,

p

) 由两个参数表示，节 ...