Python代码时间复杂度分析及优化方案技术问询

首先先贴出原函数的代码：

def complex(songs):
    for song in songs:
        one_hit = True
        for other_song in songs:
            if other_song != song and other_song.artist == song.artist:
                one_hit = False
        if one_hit:
            yield song

接下来逐个解答你的三个问题：

a) 该complex函数的时间复杂度是多少？ #

这个函数的时间复杂度是O(N²)。原因很直观：外层循环会遍历所有N首歌曲，而每一次外层循环，内层又会完整遍历所有N首歌曲，去检查当前歌手是否有其他作品。相当于执行了N*N次比较操作，属于平方级的时间复杂度——当歌曲数量N很大时，这个函数的效率会急剧下降。

b) 如何优化这个complex函数？ #

核心思路是避免重复的嵌套遍历，我们可以先一次性统计每个艺术家的歌曲数量，再基于统计结果筛选目标歌曲。具体步骤如下：

1. 遍历一次歌曲列表，用字典记录每个艺术家对应的歌曲总数；
2. 再次遍历歌曲列表，直接通过字典查询当前歌曲所属艺术家的歌曲数量，若数量为1则返回该歌曲。

优化后的代码示例：

def optimized_complex(songs):
    artist_song_count = {}
    # 第一步：统计每个艺术家的歌曲数量
    for song in songs:
        if song.artist in artist_song_count:
            artist_song_count[song.artist] += 1
        else:
            artist_song_count[song.artist] = 1
    # 第二步：筛选出所属艺术家只有一首作品的歌曲
    for song in songs:
        if artist_song_count[song.artist] == 1:
            yield song

如果喜欢更简洁的写法，也可以用collections.defaultdict来简化统计步骤：

from collections import defaultdict

def optimized_complex(songs):
    artist_song_count = defaultdict(int)
    for song in songs:
        artist_song_count[song.artist] += 1
    for song in songs:
        if artist_song_count[song.artist] == 1:
            yield song

c) 优化后的时间复杂度是多少？ #

优化后的时间复杂度是O(N)。因为我们只做了两次线性遍历：第一次遍历统计数量是O(N)，第二次筛选也是O(N)，总时间复杂度是O(N) + O(N) = O(N)，属于线性级复杂度。相比原函数的O(N²)，在数据量较大时性能提升非常明显。

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