Python函数时间/空间复杂度对比及股票最佳收益函数实现问询

嗨，关于不同Python函数的时间、空间复杂度孰优孰劣，得结合具体场景和函数类型来唠——毕竟没有绝对的“最优”，只有适合特定需求的选择。我给你举几个高频场景的例子：

• 内置函数vs自定义实现：比如Python内置的list.sort()用的是Timsort算法，时间复杂度稳定在O(n log n)，空间复杂度O(n)；要是你自己手写个冒泡排序，时间复杂度直接飙到O(n²)，虽然空间是O(1)（原地排序），但实际运行速度差了好几个量级——毕竟内置函数底层是C实现的，效率拉满。
• 列表操作的差异：list.append()是均摊O(1)的时间复杂度，因为列表扩容是预分配空间的，大部分时候直接加元素就行；但list.insert(0, x)就得把所有元素往后挪一位，时间复杂度O(n)，空间虽然也是原地，但时间成本太高。
• 字典的哈希优势：字典的get()、直接取键dict[key]平均时间复杂度都是O(1)，靠的是哈希表的快速查找；不过如果哈希冲突特别严重（极端情况），最坏会降到O(n)，但这种情况极少。空间上字典要存哈希表结构，比列表占的空间更多。
• 递归vs迭代：比如递归版斐波那契，时间复杂度是O(2ⁿ)，空间复杂度O(n)（调用栈的空间）；换成迭代版本，时间直接降到O(n)，空间O(1)，显然迭代更高效——除非逻辑特别复杂，递归的可读性优势能盖过性能劣势。

你提到的股票价格问题，咱们可以搞个O(n)时间、O(1)空间的最优解法，比暴力枚举所有买卖点（O(n²)时间）高效太多了。核心思路就是：遍历的时候只盯两个关键变量——当前遇到的最低股价，以及当前能拿到的最大收益，不用存多余的数据。

先给你写好完整的函数：

def get_best_profit(stock_prices_yesterday):
    # 先处理边界情况：至少得有两个价格才能买卖吧？
    if len(stock_prices_yesterday) < 2:
        raise ValueError("需要至少两个价格数据才能完成一次买卖操作")
    
    # 初始化：第一个价格作为初始最低买入价，第一个可能的收益作为初始最大收益
    min_price = stock_prices_yesterday[0]
    max_profit = stock_prices_yesterday[1] - stock_prices_yesterday[0]
    
    # 从第二个价格开始遍历
    for price in stock_prices_yesterday[1:]:
        # 先算如果现在卖出，能赚多少钱
        current_profit = price - min_price
        # 如果当前收益比之前的最大收益高，就更新最大收益
        if current_profit > max_profit:
            max_profit = current_profit
        # 如果当前价格比之前的最低买入价还低，就更新最低买入价
        if price < min_price:
            min_price = price
    
    # 哪怕所有价格都在跌，比如[500,400,300]，函数会返回-100——也就是亏得最少的情况（必须买卖一次）
    return max_profit

这个解法的好处是，只扫一遍列表，不用额外存其他数据，不管股价列表多长，内存占用都固定。而且逻辑也很清晰：每一步都只做“当前最优”的判断，最后得到全局的最大收益。

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