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

Question

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

Answer 1

它将使Theta(n)next调用迭代器,并添加Theta(n),其中n是你要求的项目数.

这与调用未知代码的算法的时间复杂度一样具体.如果每次添加所花费的时间取决于n(例如,当对lists 进行求和时sum(list(range(i)) for i in range(n))),那么这将影响整体时间复杂度.

Answer 2

对于大量的整数，它必须为O（n）。

Answer 3

1. 这取决于你的数据结构。对于平面列表，您不能做得比 O(n) 更好，因为您必须查看列表中的每个项目才能将它们相加。

2. 如有疑问，请尝试一下：import profile是您的朋友。