Python中降低字典成对构建操作的时间复杂度方案

你当前的实现已经达到了该问题的理论时间复杂度下界，不存在将其降到O(n)或O(n log n)级别的可能，你对嵌套循环时间复杂度的优化场景存在认知误区。

• 时间复杂度的下界由问题本身的输入输出规模决定，而非代码里写了几层循环。你需要生成的输出列表总长度为len(slots) * len(numbers)，每个输出元素都是独立的字典对象，必须单独完成构造、赋值操作，总操作数和输出元素总数完全线性相关，算法的时间复杂度下界就是Ω(m*n)（m为slots长度，n为numbers长度），你当前的写法刚好卡到这个下界，没有冗余计算。
• 你查到的嵌套循环优化方案，适用场景是两层循环做重复查找、匹配、计算，不需要生成m*n规模的输出的情况：比如求两个数组的交集、判断列表中是否存在两数之和等于目标值这类场景，确实可以通过哈希表预索引把O(mn)的复杂度降到O(m+n)，但这类方法和你当前的场景完全不匹配——你不可能跳过构造过程直接得到m*n个独立字典，就像你不可能用10次操作生成100个独立的对象。

你可以用Python内置的字典解包+列表推导式替换手写循环，依靠C层内置实现减少Python解释器层面的循环开销，实际运行速度会比你当前的写法快20%~30%，但时间复杂度依然是O(mn)：

slots = {
    "a": {"a": "Data for A"},
    "b": {"b": "Data for B"},
    "c": {"c": "Data for c"},
}
numbers = [1, 2, 3]

output = [
    {**slot, "number": num}
    for slot in slots.values()
    for num in numbers
]

如果你后续只需要遍历读取输出内容，不需要单独修改每个输出字典的属性，可以用生成器+动态视图的方式避免全量字典拷贝，把内存占用从O(mn)降到O(1)，但如果需要把结果持久化为题目要求的独立字典列表，依然需要执行和原写法等量的拷贝操作：

# 生成器写法，遍历时动态生成数据，不提前占用内存
def output_generator():
    for slot in slots.values():
        for num in numbers:
            # 注意：不要修改这里返回的对象，会直接污染原slots里的字典
            yield slot | {"number": num}

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