Python中条件判断使用多个in运算符的时间复杂度差异分析

假设我们需要检查3个元素（'a'、'b'、'c'）是否存在于可迭代对象（以字符串为例，列表场景逻辑一致）中，待搜索字符串为'abcd'并存储在变量line中，常见两种实现方式如下：

方式一：多次直接判断 #

if 'a' in line and 'b' in line and 'c' in line:
    # 执行操作
    pass

方式二：使用all()函数 #

if all(sub_str in line for sub_str in ['a','b','c']):
    # 执行操作
    pass

时间复杂度分析 #

这两种实现的时间复杂度本质一致，均为O(n*k)（其中n是可迭代对象的长度，k是待检查元素的数量），具体原因如下：

• 方式一中，每个x in line操作对字符串/列表这类线性结构来说都是线性扫描（O(n)），三个检查累加为O(3n)，忽略常数系数后就是O(n)。同时由于and的短路特性，只要某一个元素不存在，后续检查会直接终止。
• 方式二中，all()函数会遍历生成器表达式内的元素，每次执行sub_str in line同样是线性扫描。all()本身也具备短路特性——一旦遇到不存在的元素，立即停止后续检查，和方式一的短路逻辑完全匹配。

两者仅存在常数级的执行开销差异（生成器表达式带来的细微解释器成本），但这不会改变时间复杂度的量级，在绝大多数业务场景下可以忽略不计。

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