Python的max函数有多高效

Question

函数max()返回列表中的最大元素。就Big O notation而言，它的运行时间（在Python 3中）是多少？

Answer 1

这取决于你如何使用它。 如果要基于函数“someFunc”最大化，则需要O(len(l)*k)，其中k是函数“someFunc”运行所需的时间。

maxVal = max(l, key=somefunc)

但对于普通情况，它应该只是遍历列表，并使用普通比较函数找到最大值。

Answer 2

当然，它是O（n），除非由于某些实现不变量而使用支持值集合最大值的不同数据结构。

Answer 3

它是O（n），因为它必须检查每个元素。如果希望max有更好的性能，可以使用heapq模块。但是，您必须negate each value，因为heapq提供最小堆。在堆中插入元素是O（log n）。