内层长度可变的两组独立嵌套循环的Big-O时间复杂度是多少

这段代码的平均Big-O时间复杂度为 O(A_total + B_total)，属于线性复杂度范畴。

具体推导 #

• 复杂度计算的基本逻辑很直白：串行执行的代码，总开销是各段开销的和；嵌套循环的开销，和所有层级实际遍历到的元素总规模正相关，只要内层执行的是常数级操作，整体开销就和总遍历元素数呈线性关系。
• 先看第一段遍历struct_a的双层循环：没必要硬套“外层长度N、内层平均长度M所以复杂度是O(N*M)”的固定公式，毕竟题目明确说了各层长度可变、最小可以是0，直接统计这段循环实际会访问到的sub元素总个数即可，我们把这个总数记为A_total。不管是struct_a本身长度为0，还是所有row下的subAttr长度为0，A_total都是0，和实际运行时这部分完全无开销的表现完全匹配。
• 第二段遍历struct_b的双层循环和前者完全独立、串行执行，同理统计这段循环实际访问的sub元素总个数，记为B_total。
• 循环内部执行的哈希表查找操作，平均场景下时间复杂度为O(1)（常数级），不会改变整体复杂度的量级。只有出现极端哈希冲突的最坏情况，单次查找才会退化为线性，常规工程场景下的复杂度评估，默认取平均情况的常数时间计算即可。

常见误区提醒：不要看到双层循环就直接把所有层长度乘到一起算复杂度——首先单组嵌套循环的乘积结果本质就是内层遍历元素的总个数，也就是我们定义的A_total、B_total；其次这两组嵌套循环是先后串行执行的，不是互相嵌套的关系，所以总复杂度是两部分规模相加，不是把四个循环的长度全部相乘。

对应分析的代码片段如下：

# struct_a has unbounded length, but could be zero
for row in struct_a:

    # row.subAttr has unbounded length, but could be zero
    for sub in row.subAttr:
        # 执行平均O(1)的哈希表查找
        ...

# struct_b has unbounded length, but could be zero
for row in struct_b:

    # row.subAttr has unbounded length, but could be zero
    for sub in row.subAttr:
        # 执行平均O(1)的哈希表查找
        ...

内容的提问来源于stack exchange，提问作者rodrigo-silveira