从 O(n^2) 到 O(n) 的最大减少列表

Question

我的程序复杂度为 O(n^2)。我想要复杂度为 O(n) 的程序图。我怎样才能做到这一点？

我的程序背后的想法是，与该元素之后的元素相比，我希望列表中某个元素的减少量最大。

因此，例如列表 [4,7,5,8,4,3] 将元素 4 与 7,5,8,4,3 进行比较，并将元素 8 与 4,3 进行比较。解决方案是； 8-3 = 5（最大跌幅）。

def grootste_daling(temperaturen):
    afname = []
    for i in range(len(temperaturen)):
        for j in range(i + 1, len(temperaturen),1):
                if temperaturen[i] - temperaturen[j] > 0:
                    afname.append(temperaturen[i] - temperaturen[j])
    return max(afname) if afname else 0

Answer 1

是的，这在线性时间内是可以解决的。您只需要跟踪目前看到的最大元素：

    maximum = 0
    max_decrease = 0
    for current in temperatures:
        if current > maximum:
            maximum = current
        if maximum - current > max_decrease:
            max_decrease = maximum - current

（0的初始值假定列表的值为正并且实际会减少。否则可能需要对变量进行不同的初始化。）

从 O(n^2) 到 O(n) 的最大减少列表

biggest decrease list from O(n^2) to O(n)

python

complexity-theory