Python的max函数有多高效

Question

函数

max()

返回列表中的最大元素。 。 。以 Big O 表示法 表示的运行时间（在 Python 3 中）是多少？

Answer 1

它的复杂度是 O(n)，因为它必须检查每个元素。 如果您想要 max 获得更好的性能，可以使用 heapq 模块。 但是，您必须否定每个值，因为

heapq

提供了最小堆。将一个元素插入堆中的时间复杂度为 O(log n)。

Answer 2

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

Answer 3

这取决于您如何使用它。 如果您想基于函数“someFunc”最大化，则需要

O(len(l)*k)

，其中 k 是“someFunc”的时间复杂度。

maxVal = max(l, key=somefunc)

但是，对于正常情况，它应该只迭代列表并使用正常比较函数找到最大值。