Python 中 sum() 的时间复杂度是多少？

Question

sum() 函数的时间复杂度是多少？

原文由 lzc 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

它将使 Theta(n) next 调用迭代器和 Theta(n) 添加，其中 n 是您要求和的项目数。

对于调用未知代码的算法的时间复杂度，这非常具体。如果每次添加所花费的时间取决于 n （例如在求和时它会 list s，比如 sum(list(range(i)) for i in range(n)) 时间复杂度。

原文由 Steve Jessop 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

对于一个大的整数列表，它必须是 O(n)。

原文由 dstromberg 发布，翻译遵循 CC BY-SA 3.0 许可协议