Python RadixSort复杂度评估：big_o为何判为指数复杂度而非O(b*n)

你的复杂度测试结果异常，首要原因是RadixSort实现存在状态残留bug，其次是big_o测试参数配置不合理。

1. 核心bug：排序桶未在每次排序前清空 #

你将桶数组self.buckets的初始化放在__init__方法中，整个实例生命周期内仅初始化一次，但每次调用sort()时没有清空桶内上一次排序残留的旧数据：

• 新元素会被追加到存有旧数据的桶中，合并后得到的列表长度远大于当前输入的n
• 多轮基数位循环下来，残留数据会持续累积，实际处理的数据量随测试调用次数快速上涨，最终被big_o误判为指数复杂度
• 这个bug同时会导致排序结果完全错误，单独跑两次不同长度的用例，打印返回结果就能看到大量重复脏数据。

修复方案是把桶的初始化逻辑移到sort()方法开头，每次排序创建全新的空桶，不要复用实例属性的桶：

def sort(self, list1d):
    """
    Sorts a given 1D-list using radixsort in ascending order
    @param list1d to be sorted
    @returns the sorted list as an 1D array
    @raises ValueError if the list is None
    """
    if list1d is None: raise ValueError('List mustn\'t be None')
    if len(list1d) in [0, 1]: return list1d
    # 每次排序初始化全新的空桶，删除原__init__中的buckets初始化逻辑即可
    buckets = [[[] for _ in range(10)] for _ in range(self.base)]

    for b in range(self.base):
        for n in list1d:
            digit = (n // (10 ** b)) % 10
            buckets[b][digit].append(n)
        list1d = self.itertools_chain_from_iterable(buckets[b])

    return list1d

2. big_o测试参数配置问题 #

当前测试配置存在两个问题，也会导致拟合结果偏差：

• n_measures=10采样点太少，复杂度拟合依赖多组(规模n, 运行时间)的采样点做回归，采样点越少越容易被系统噪声干扰出现误判，建议调到20以上
• 未指定测试的n范围，默认生成的测试规模分布可能不合理，建议手动指定n的上下限，覆盖目标测试区间

调整后的测试代码参考：

print('r.sort complexity:',big_o.big_o(
    r.sort,
    lambda n: big_o.datagen.integers(n,1,9999999),
    n_measures=25,
    min_n=100,
    max_n=20000,
)[0])

额外说明 #

你当前把self.base固定写为7，刚好匹配测试用例1~9999999的7位数值范围，如果后续需要排序更大的数，要动态计算输入列表的最大位数作为base，否则会出现排序错误，不过这个问题不影响当前场景下的复杂度测试结果。

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