含多条件if判断的嵌套for循环的Time complexity计算问题

首先对原代码做合理修正（原示例中i.append(list)属于语法逻辑笔误，i为遍历出的元素不可调用append方法，修正为向结果列表追加元素的常规写法）：

# 定义结果存储列表
res = []
for i in list1:
    if i in list2:
        if i not in list3:
            res.append(i)

分析前提约定 #

我们先定义三个输入列表的长度：

• list1长度为n
• list2长度为m
• list3长度为k

理想场景默认采用最优实现：提前将list2、list3转换为哈希集合（如Python中的set），成员查询操作的时间复杂度为O(1)。

理想时间复杂度计算 #

1. 预处理阶段：转换list2为哈希集合耗时O(m)，转换list3为哈希集合耗时O(k)
2. 遍历执行阶段：遍历list1的所有n个元素，每个元素最多执行2次O(1)的成员查询，命中条件后的列表追加操作均摊复杂度也为O(1)，该阶段总耗时O(n)
3. 整体理想时间复杂度为：O(n + m + k)

非理想场景补充（无预处理直接用列表查询） #

如果不做哈希预处理，直接对列表执行in/not in成员查询，每次查询的时间复杂度等于被查询列表的长度：

• 最坏情况下list1的所有元素都存在于list2中，每次遍历需要先做*O(m)的list2成员查询，再做O(k)*的list3成员查询
• 整体时间复杂度为：O(n(m + k))*

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