时间戳

首页 > 解决方案 > 从 O(n^2) 到 O(n) 的最大减少列表

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

问题描述

我的程序复杂度为 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

标签： pythoncomplexity-theory

解决方案

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

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

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

推荐阅读