Python嵌套列表扁平化去重函数f2的时间复杂度分析

相对于总元素数量N，如下Python代码的时间复杂度为多少？
待分析函数的功能为将嵌套整数列表（List[List[int]]）扁平化为单个列表，移除重复元素且仅保留每个元素的首次出现项，函数实现代码如下：

def f2(list_of_list):
    flat_list = []
    for inner_list in list_of_list:
        flat_list.extend(inner_list)
    return [
        x for i, x in enumerate(flat_list)
        if flat_list.index(x) == i]

该代码的时间复杂度为 O(N²)。

我们拆分成两个执行阶段分别计算复杂度，最终取最高阶项作为整体复杂度：

• 第一阶段：列表扁平化
  代码通过循环遍历外层嵌套列表，调用extend将所有子列表的元素追加到flat_list中，整个过程会完整遍历全部N个元素，这一阶段的时间复杂度为O(N)。
• 第二阶段：列表推导式去重
  这部分是复杂度的主要来源：
  1. 推导式本身会遍历flat_list的全部N个元素，共执行N轮迭代；
  2. 每轮迭代中调用的list.index(x)方法是线性扫描操作：它会从列表头部开始逐个比对元素，直到找到第一个和x相等的值才返回对应索引，单次调用的最坏时间复杂度为O(N)；
  3. 当列表所有元素均不重复时（最坏情况），每轮index调用都需要扫描到当前元素所在位置才能匹配成功，总比对次数为1+2+3+...+N = N(N+1)/2，这一阶段的时间复杂度为O(N²)。

两个阶段的复杂度取最高阶，最终整体时间复杂度为O(N²)。

补充说明：如果列表存在大量重复元素，index会更早找到匹配项，实际运行耗时会比最坏情况低，但时间复杂度的上界依然是O(N²)。

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