Python big_o模块测算时间复杂度返回错误结果的原因排查

问题现象 #

使用big_o模块对比4种嵌套列表扁平化实现方案的时间复杂度时，返回的测算结果完全不符合理论预期，具体异常如下：

• 基于itertools.chain.from_iterable实现的扁平化方法，代码如下：

def itertools_chain_from_iterable(arr): 
    return list(chain.from_iterable(arr))

被判定为常数（Constant）复杂度，结论明显不符合逻辑。

• 基于列表extend方法实现的merge_extend方法，代码如下：

def merge_extend(self,arr):
    output = []
    for l in arr:
        output.extend(l)
    return output

被判定为三次（Cubic）复杂度，理论上该方法复杂度最高仅为二次。

• 基于sum函数实现的merge_w_sum方法，代码如下：

def merge_w_sum(self,arr): 
    return sum(arr,[])

被判定为线性（Linear）复杂度，但已有公开技术验证该方法实际为二次复杂度。

• 基于列表推导式实现的merge_bucket方法，代码如下：

def merge_bucket(self,bucket):
    return [number for n in bucket for number in n]

被判定为多项式（Polynomial）复杂度，理论上该方法应为线性复杂度。

测试代码与运行输出 #

本次测试使用的测算代码如下：

print('<function name>:', big_o.big_o(<function name>, 
       lambda n:[big_o.datagen.integers(9900,1,9999999) for n in range(50)],
       n_measures=20)[0])

实际运行得到的输出：

complexity of itertools_chain_from_iterable: Constant: time = 0.0013 (sec)
complexity of merge_w_sum: Linear: time = 0.46 + 6.2E-07*n (sec)
complexity of merge_extend: Cubic: time = 0.048 + -2.3E-18*n^3 (sec)
complexity of merge_bucket: Polynomial: time = 0.2 * x^-0.019 (sec)

错误原因 #

所有结果失准的核心问题是测试逻辑存在根本性错误，和big_o模块本身、算法复杂度理论认知无关：

1. 测试数据生成逻辑完全失效
   big_o工作原理是传入不同规模的n值给数据生成函数，得到不同大小的测试输入，再记录不同输入下的函数运行耗时，最后拟合耗时-输入规模的曲线得到复杂度结果。但你写的生成函数完全没有使用传入的n参数控制输入规模：无论传入的n是100还是100000，永远固定生成50个长度为9900的整数列表，输入总规模全程恒定，没有任何规模梯度。拟合模型拿到的是一组输入规模不变、耗时只有随机波动的数据点，自然会输出完全随机的错误复杂度判定。
   比如itertools实现本身运行速度最快，不同次测试的耗时波动极小，就被拟合为常数复杂度；merge_extend的三次项系数小到-2.3E-18，本质是拟合平线时硬套模型产生的无效结果；merge_bucket得到的x^-0.019结果，指数接近0，本质也是对水平波动数据的无效拟合。
2. 测试方法存在额外隐患
   你写的后三个方法都是带self参数的类实例方法，如果直接传入未绑定实例的方法对象，调用时会因为缺少self参数报错，说明测试时要么做了错误的方法绑定，要么传入的函数对象和你贴出的代码不一致，也会干扰测试结果。

修正方案 #

重新编写符合要求的测试数据生成器，确保输入规模随传入的n值线性增长，示例如下：

import random
def generate_nested_list(total_elements):
    # 生成总元素数约为total_elements的嵌套列表，内层列表长度随机
    nested = []
    remaining = total_elements
    while remaining > 0:
        sub_len = random.randint(1, min(1000, remaining))
        nested.append(big_o.datagen.integers(sub_len, 1, 9999999))
        remaining -= sub_len
    return nested

测试时将n_measures调整到30以上，让测试覆盖1000到100000总元素数的规模梯度，同时传入正确绑定的函数对象，即可得到符合理论预期的复杂度结果。

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