我在这个视频中看到，使用以下算法计算星形图中心节点的聚类系数是theta(n^2)，而对于团图则是theta(n^3)。这是正确的吗？

def clustering_coefficient(G,v):    neighbors = G[v].keys()    if len(neighbors) == 1: return 0.0    links = 0.0    for w in neighbors:        for u in neighbors:            if u in G[w]: links += 0.5    return 2.0*links/(len(neighbors)*(len(neighbors)-1))

回答：

复杂度取决于图的密度以及in谓词的效率。

在完全图上进行的简单实现显然是O(n^3)：两个嵌套循环和一个in谓词，每个都以线性时间运行。如果你将链接保存在哈希映射中（而不是在密集矩阵表示中！），那么运行时间仅为O(n^2) – 对于单个节点而言。但通常，这种算法会应用于每个节点，从而增加另一个n因子。

如果你的图不是完全图（并且你使用了更有效的in谓词），事情会变得快得多。假设每个节点有sqrt(n)个邻居，算法的复杂度将是O(sqrt(n)^2)*n（对于所有节点而言），这可能是他们O(n^2)的结果。

假设每个节点恰好有两个邻居。那么复杂度可以很容易地降到O(1) * n。哦，如果每个节点有0个邻居，那就更简单了。