min（）的空间复杂度是多少？

Question

我在面试蛋糕中解决了一个问题，并提出了通过单元测试的解决方案。

def get_max_profit(stock_prices):
    # Calculate the max profit
    if(len(stock_prices) == 0):
        raise ValueError('Empty stock')
    elif(len(stock_prices) == 1):
        return stock_prices[1]

    minValue = min(stock_prices)
    index_min = stock_prices.index(minValue)
    maxValue = max(stock_prices)
    index_max = stock_prices.index(maxValue)

    if(minValue == maxValue):
        return 0
    elif(index_max < index_min):
        return (stock_prices[1]-stock_prices[0])

    return (maxValue-minValue)

所以我在代码中使用了min，max函数。那么，使用列表中的min，max等内置函数的空间复杂度是多少？它们如何在内部工作（我正在使用python 3.6）

Answer 1

空间复杂度取决于您的可迭代输入的类型（即示例中stock_prices的类型）。如果您输入的是一个列表（或具有随机访问权限的其他类似可索引数据结构），那么您已经将整个数据结构放入了内存，即O（n）。

另一方面，如果您输入的是生成器（或类似类型），可以lazily进行评估，则min / max可以一次检查每个元素而不会进行转储，然后整个可迭代的内存，即O（1）。

（注意，min / max的时间复杂度当然是O（n）。]