Python多层循环列表推导式写法修复及算法效率计算相关问题

你之前写法出错的核心原因：

• list.append() 是原地修改方法，返回值固定为None，所以你在推导式中调用append自然会得到全是None的列表
• 第二种写法存在语法错误：append是函数方法不是可索引序列，不能用[]访问，写法本身不合法

你可以直接优化原逻辑的冗余部分，把循环范围限定为各变量的合法区间，省掉多余的边界判断和无效循环，最终正确的推导式版本如下：

def perm(x,y,z,n):
    return [[i, j, k] for i in range(x + 1) 
            for j in range(y + 1) 
            for k in range(z + 1) 
            if i + j + k != n]

测试调用print(perm(1,1,2,3))和你原来的循环版本输出完全一致。

效率计算通用标准 #

行业通用的算法效率衡量标准是大O时间复杂度，它描述的是算法运行时间随输入规模增长的变化趋势，计算时忽略常数项、低阶项，只保留最高阶的影响因子：

• 你最初的循环版本：三层循环每层最多遍历x+y+z次，时间复杂度为O((x+y+z)³)，你的测试用例中总循环次数是4*4*4=64次
• 上面优化后的推导式版本：三层循环每层遍历次数分别为x+1、y+1、z+1，时间复杂度为O(x*y*z)，同样的测试用例总循环次数只有2*2*3=12次，性能提升了数倍

如果进一步优化，固定i和j后直接计算k的合法取值范围，不需要遍历所有k，时间复杂度可以降到O(x*y)，输入规模越大性能提升越明显。

优化判断标准 #

判断是否需要优化可以参考两个维度：

1. 实际输入规模：如果x、y、z都是个位数的小数值，不管怎么写运行耗时都可以忽略，不需要额外优化；如果输入规模达到几十上百，三层循环的耗时会呈立方级上涨，就需要做优化
2. 业务耗时要求：如果这段代码是核心高频调用逻辑，哪怕单次节省1ms，累计下来收益也很高，就值得优化；如果是偶尔运行的工具脚本，只要结果正确就可以不用改。

学习资源推荐 #

入门可以看《算法图解》，对时间复杂度的讲解非常通俗易懂；系统学习可以看国内高校通用的《数据结构与算法》教材，进阶可以参考《算法导论》，里面覆盖了所有通用的算法效率计算、优化思路的内容。

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