推导式是否具有与显式 for 循环相同的渐近复杂性？

Question

在大多数情况下，使用列表/字典推导式在对代码进行计时时可以显着提高性能，但是它会影响算法的渐近复杂度吗？

据我了解，差异是由于与显式循环相比推导式的评估方式造成的，但这种差异应该是一个常数因子，在这种情况下，渐近复杂性不会改变，然后随着问题规模的增加，存在最终应该会达到两个版本以相同速度执行的程度。我的想法正确吗？

与此同时，当我尝试测试它时，推导式的表现一直优于显式循环，直到我达到内存不足的大小。

Answer 1

很好的问题，但这不是渐近复杂性的工作原理。这并不是说它们会收敛到相同的时间，而是它们都会以相同的方式增长。例如，采用 2*n 和 n 的算法具有相同的渐近复杂度，但前者总是需要两倍的时间。我看不出为什么推导式不会具有相同的复杂性，但您可以通过计时测试来凭经验进行测试。