为什么最大比sorting慢？
我发现max比Python 2和3中的sort函数慢。
Python 2
$ python -m timeit -s 'import random;a=range(10000);random.shuffle(a)' 'a.sort();a[-1]' 1000 loops, best of 3: 239 usec per loop $ python -m timeit -s 'import random;a=range(10000);random.shuffle(a)' 'max(a)' 1000 loops, best of 3: 342 usec per loop
Python 3
$ python3 -m timeit -s 'import random;a=list(range(10000));random.shuffle(a)' 'a.sort();a[-1]' 1000 loops, best of 3: 252 usec per loop $ python3 -m timeit -s 'import random;a=list(range(10000));random.shuffle(a)' 'max(a)' 1000 loops, best of 3: 371 usec per loop
为什么max （ O(n) ）比sort函数（ O(nlogn) ）慢呢？
在Python中使用timeit模块时必须非常小心。
python -m timeit -s 'import random;a=range(10000);random.shuffle(a)' 'a.sort();a[-1]'
这里的初始化代码运行一次产生一个随机数组a 。 然后其余的代码运行几次。 第一次对数组进行sorting，但是每隔一段时间您就对已经sorting好的数组调用sorting方法。 只返回最快的时间，所以你实际上计时需要多长时间Pythonsorting已经sorting的数组。
Python的sortingalgorithm的一部分是检测数组何时已经部分或完全sorting。 当完全sorting它只需要扫描一次数组来检测这个，然后停止。
如果您尝试：
python -m timeit -s 'import random;a=range(100000);random.shuffle(a)' 'sorted(a)[-1]'
那么就会在每个时序循环中进行sorting，您可以看到sorting数组的时间确实比find最大值要长得多。
编辑： @ skyking的答案解释了我不知道的部分： a.sort()知道它正在一个列表上，所以可以直接访问元素。 max(a)工程任何可迭代的，所以必须使用generics迭代。
首先，请注意， max()使用迭代器协议 ，而list.sort()使用专用代码 。 显然，使用迭代器是一个重要的开销，这就是为什么你观察时间的差异。
但是，除此之外，你的testing是不公平的。 您在同一个列表上多次运行a.sort() 。 Python使用的algorithm专门为已经（部分）sorting的数据而devise。 你的testing说这个algorithm做得很好。
这些都是公平的testing：
$ python3 -m timeit -s 'import random;a=list(range(10000));random.shuffle(a)' 'max(a[:])' 1000 loops, best of 3: 227 usec per loop $ python3 -m timeit -s 'import random;a=list(range(10000));random.shuffle(a)' 'a[:].sort()' 100 loops, best of 3: 2.28 msec per loop
在这里，我每次创build一个列表的副本。 正如你所看到的，结果的数量级是不同的：我们所期望的是微秒对毫秒。
请记住：大哦指定一个上限！ Pythonsortingalgorithm的下界是Ω（ n ）。 作为O（ n log n ）并不意味着每次运行都需要一个与n log n成比例的时间。 这甚至不意味着它需要比O（ n ）algorithm慢，但这是另一回事。 重要的是要理解，在一些有利的情况下，O（ n log n ）algorithm可以在O（ n ）或更less的时间内运行。
这可能是因为l.sort是list的成员，而max是通用函数。 这意味着l.sort可以依赖list的内部表示，而max将不得不通过通用迭代器协议。
这使得每个元素获取l.sort比获取max每个元素更快。
我假设，如果你使用sorted(a)你会得到比max(a)慢的结果。
