如何在Python中避免二次时间复杂度？寻找共享演员最多的电影对

我用NetworkX构建了一个二分图G，节点包含电影和演员，演员参演某部电影时两者之间存在边。现在需要找出共享演员数量最多的电影对，手头有所有演员和电影的字典数据。

最初实现的问题 #

最初的思路是遍历每个演员，获取其参演的所有电影，再对每对电影计数：

maximum=0        
pair=[]
dict_pair_movies={}            
for actor in actors:
    list_movies=list(nx.all_neighbors(G, actor))
    for movie1 in list_movies:
        for movie2 in list_movies:
            if movie1!=movie2:
                dict_coppia_movies[(movies1,movies2)]+=1                 
                if dict_coppia_movies[(movies1,movies2)]>massimo:
                    maximum=dict_coppia_movies[(movies1,movies2)]
                    pair=[movies1,movies2]
return pair 

这个方案在200万演员的数据集上完全不可行，小数据集测试还暴露两个问题：

• 直接使用dict_coppia_movies[(movies1,movies2)]+=1会触发KeyError，必须改用dict_coppia_movies[(movies1,movies2)]=dict_coppia_movies.get((movies1,movies2),0) + 1才能正常计数；
• 无法识别(A,B)和(B,A)是同一电影组合，会生成两个独立字典键，造成重复计数和资源浪费。

后续尝试用nx.common_neighbors获取两部电影的共同演员数，但始终无法避免二次时间复杂度，也没法只遍历不重复的电影对。

待验证的优化尝试 #

后来尝试了一个基于nx.common_neighbors的实现，想用zip结合电影列表和集合遍历：

movieList=list(movies.keys())
movieSet=set(movieList)   
     
def question3():
    maximum=0
    pair=[]
    for node1,node2 in zip(movies,movieSet):
        neighborsList=(list(nx.common_neighbors(G,node1,node2)))
        if len(neighborsList)>maximum:
            maximum=len(neighborsList)
            pair=[node1,node2]
    
    return pair

代码返回了结果，但无法确认正确性。已知zip会截断到较短序列的长度，这里movies和movieSet长度相同，理论上能遍历所有电影，但不确定是否覆盖了所有可能的电影对。

正确的优化方案 #

核心思路 #

利用二分图的特性（演员和电影分属两个不相交节点集合），重点解决重复遍历和效率问题：

1. 只遍历不重复的电影对（避免(A,B)和(B,A)重复计算）；
2. 用更高效的方式计算共同演员数；
3. 直接在遍历过程中跟踪最大值，无需存储所有计数（节省内存）。

基础优化代码 #

from itertools import combinations
import networkx as nx

def find_most_shared_actor_pair(movies, G):
    movie_list = list(movies.keys())
    max_count = 0
    best_pair = None
    
    # 生成所有不重复的电影对（i<j）
    for movie_a, movie_b in combinations(movie_list, 2):
        # 计算共同演员数量
        common_actor_num = len(list(nx.common_neighbors(G, movie_a, movie_b)))
        if common_actor_num > max_count:
            max_count = common_actor_num
            best_pair = (movie_a, movie_b)
    
    return best_pair, max_count

进一步优化（超大电影数据集） #

如果电影数量也很大，预构建电影到演员的集合映射，用集合交集计算共同演员数会更快：

from itertools import combinations
import networkx as nx

# 预构建电影到演员的集合映射
movie_to_actors = {}
for movie in movies.keys():
    movie_to_actors[movie] = set(nx.all_neighbors(G, movie))

def find_most_shared_actor_pair(movies, movie_to_actors):
    movie_list = list(movies.keys())
    max_count = 0
    best_pair = None
    
    for movie_a, movie_b in combinations(movie_list, 2):
        # 集合交集的长度就是共同演员数量
        common_actor_num = len(movie_to_actors[movie_a] & movie_to_actors[movie_b])
        if common_actor_num > max_count:
            max_count = common_actor_num
            best_pair = (movie_a, movie_b)
    
    return best_pair, max_count

集合交集的计算是底层优化过的，比调用nx.common_neighbors遍历节点快得多，适合超大数据集。

内容的提问来源于stack exchange，提问作者johan14