Python maxProfit函数的时间复杂度分析及优化方法咨询

一、时间复杂度分析 #

你原以为是O(n³)，其实不对。这个函数的时间复杂度是O(n²)，原因如下：

• 外层for循环执行n次（n是prices数组的长度）；
• 内层for循环的执行次数随外层的i变化：当i=0时执行n-1次，i=1时执行n-2次……直到i=n-1时执行0次，总执行次数是(n-1)+(n-2)+...+1 = n(n-1)/2，这是二次方级别的运算量；
• 循环里的if判断和赋值都是O(1)的常数操作，不会改变整体的时间复杂度阶数。

二、优化方案 #

可以把时间复杂度降到O(n)，只需要一次遍历即可：
核心思路是遍历过程中记录当前遇到的最小价格，同时计算当前价格与最小价格的差值，实时更新最大利润。这样避免了嵌套循环的重复计算。

优化后的代码：

def maxProfit(self, prices: List[int]) -> int:
    if not prices:
        return 0
    min_price = prices[0]
    max_profit = 0
    for price in prices[1:]:
        if price < min_price:
            min_price = price
        else:
            current_profit = price - min_price
            if current_profit > max_profit:
                max_profit = current_profit
    return max_profit

优化逻辑说明： #

• 初始化min_price为数组第一个元素，max_profit为0；
• 从第二个元素开始遍历，每遇到比当前min_price更低的价格，就更新min_price；
• 如果当前价格高于min_price，就算出当前利润，和max_profit比较后更新；
• 整个过程只遍历数组一次，空间上只用到几个变量，空间复杂度是O(1)。

内容的提问来源于stack exchange，提问作者Andri