Python的max函数效率如何

Question

函数 max() 是用来从一个列表中找出最大值的。那么，在 Python 3 中，这个函数的运行时间用大O符号表示是怎样的呢？

Answer 1

这要看你怎么使用它了。
如果你想根据一个叫“someFunc”的函数来找最大值，那么这个过程的时间复杂度是 O(len(l)*k)，其中 k 是“someFunc”运行所需的时间。

maxVal = max(l, key=somefunc)

不过在一般情况下，它只需要遍历列表，使用普通的比较方法来找到最大值。

Answer 2

当然，这个操作的复杂度是O(n)，除非你使用了其他的数据结构，这种数据结构能够在某些实现条件下支持一组值中的最大值。

Answer 3

这个算法的复杂度是O(n)，因为它需要检查每一个元素。如果你想要更快地找到最大值，可以使用heapq模块。不过，你需要将每个值取反，因为heapq提供的是一个最小堆。往堆里插入一个元素的复杂度是O(log n)。