Python列表取最大值两种方法的性能对比及场景分析

一、基础场景：直接取列表最大值的两种实现对比 #

给定列表 arr = [1,6,0,9,3,12,8,5]，两种取最大值的写法：

1. 内置函数法

x = max(arr)

2. 迭代逐次比较法

x = 0
for ele in arr:
    x = max(x, ele)

复杂度分析 #

• 时间复杂度：两种方法都是 O(n)。内置max(arr)底层是C实现的一次遍历比较；循环逐次比较是Python层面的遍历，本质都需要遍历整个列表n次，复杂度量级相同。
• 空间复杂度：都是 O(1)，仅用单个变量存储最大值，无额外规模相关的空间开销。

性能差异与最优方案 #

• 内置max(arr)的实际速度远快于Python循环版：因为内置函数由C实现，绕过了Python解释器的循环、函数调用开销。
• 循环中每次调用max(x, ele)，比直接用if ele > x: x = ele慢，原因是每次调用max都有函数调用的额外成本（栈帧创建、参数传递等）。
• 最优方案毫无疑问是内置max(arr)：代码简洁，执行效率最高。

关于时间复杂度的疑问 #

循环中每次调用max(x, ele)的时间复杂度仍是O(n)，和内置max(arr)量级相同，但实际速度更慢——慢在常数项开销，而非复杂度量级。

二、进阶场景：筛选元素并同步跟踪最大值的对比 #

需求是筛选出能被3整除的元素生成新列表，同时跟踪最大值，两种实现：

1. 先筛选再取最大值

newArr = []
for ele in arr:
    if ele%3 == 0:
        newArr.append(ele)
x = max(newArr)

2. 筛选时同步更新最大值

newArr = []
x = 0
for ele in arr:
    if ele%3 == 0:
        newArr.append(ele)
        if ele > x:
            x = ele

复杂度分析 #

• 第一种方法：遍历原列表是O(n)，调用max(newArr)是O(k)（k为筛选后新列表长度，k≤n），总复杂度为O(n + k)，等价于O(n)（k最大等于n）。
• 第二种方法：仅遍历原列表一次，符合条件时做一次比较，总复杂度也是O(n)。

两者时间复杂度量级相同，差异仅在常数项。

实测现象解析 #

• if ele > x: x = ele比x = max(x, ele)快很多：前者是原生Python条件判断+赋值，无函数调用开销；后者每次都要触发max函数调用，额外成本高。
• if ele > x略快于max(newArr)：前者在一次遍历中完成筛选和最大值更新，避免了max(newArr)需要的第二次遍历（遍历新列表），常数项开销更小。
• 嵌套列表场景内置max(arr)更快：嵌套列表下，手写Python多层循环的解释器开销极大，而内置max用C实现遍历，能大幅减少这类开销，优势被放大。

内容的提问来源于stack exchange，提问作者Mr.Bagel