减少列表操作的复杂性

Question

我遇到了一个Python问题需要解决，我解决了，但有人批评我的方案性能不好……所以我想在这里分享一下，看看有没有可能的改进：

这个问题非常简单，就是要找出一个列表的前半部分和后半部分的和之间的最小绝对差。

举个例子，如果我们有：

L = [3, 1, 2, 4, 3]

我们可以把这个问题分成四个步骤：

i = 1, abs difference = |3 − 10| = 7 
i = 2, abs difference = |4 − 9| = 5 
i = 3, abs difference = |6 − 7| = 1 
i = 4, abs difference = |10 − 3| = 7 

在这个例子中，脚本应该返回1，作为最小的绝对差。

正如我所说，这对我来说很简单，我做到了：

def get_minAbsDiff(L):
    return min([abs(sum(L[0:i+1]) - sum(L[i+1:])) for i in xrange(len(L)-1)])

然而，似乎这个方案的时间复杂度是O(N*N)，也就是比较慢。

有没有可能把这个问题的复杂度降到O(N)呢？

编辑：

是别人告诉我这个O(N*N)的复杂度，我其实不太确定这个说法对不对。

相关文章：

• 暂无相关问题

Answer 1

我知道这里已经有很多解决方案了。只是想补充一个在时间和空间上都最简单的算法。

testList = [1,2,3,4,5]

totalSum = sum(testList)

currentSum = 0
minDiff = totalSum

for a in testList:
    currentSum += a
    minDiff = min( abs(totalSum - currentSum - currentSum), minDiff)

print minDiff

Answer 2

L = [3, 1, 2, 4, 3]
sec_part = sum(L)
diff = []
for i in L:
    diff.append(abs(sec_part - i * 2))
    sec_part -= i * 2
print min(diff)

首先，把整个列表的所有数字加起来，这个过程的复杂度是 O(N)，意思是说处理的时间和列表里有多少个数字成正比。

其次，使用一个循环来减少这个值。注意：我们要减少的是每个数字的两倍，因为在第一步的时候我们已经把它加上去了。这个循环的时间复杂度也是 O(N)。

最后，使用 min 函数来找出最小的值，这个过程的时间复杂度同样是 O(N)。

Answer 3

你可以通过一次移动一个数值，从右边的总和转到左边的总和，来逐步计算总和。

下面是我会怎么写的，sums 函数会把 xs 中的所有数分成左边和右边，并计算它们的总和。

def sums(xs):
    left, right = 0, sum(xs)
    for x in xs:
        yield left, right
        left += x
        right -= x
    yield left, right

def min_abs_diff(xs):
    return min(abs(left - right) for left, right in sums(xs))

print min_abs_diff([3, 1, 2, 4, 3])

Answer 4

要实现O(N)的解决方案，关键在于你在遍历列表的时候，其实是在一个总和上减去一些值，同时在另一个总和上加上这些值。所以……

def get_minAbsDiff(L):
    leftSum = 0
    rightSum = sum(L)
    minDiff = rightSum

    for i in L:
        leftSum += i
        rightSum -= i
        diff = abs(leftSum-rightSum)

        if diff < minDiff: minDiff = diff

    return minDiff

Answer 5

你不需要一直把所有元素加起来。只需一次计算出总和，然后在循环中更新这个总和：

def min_abs_diff(L):
    sum1, sum2 = 0, sum(L)
    min_abs_diff = float('inf')  # sentinel value
    for i in L:
        sum1 += i
        sum2 -= i
        abs_diff = abs(sum1 - sum2)
        if min_abs_diff > abs_diff:
            min_abs_diff = abs_diff
    return min_abs_diff

所以你一开始有 0 和 13，然后在循环中，这个值会变成 3 和 10，因为你把 i 的值从一个总和转移到另一个总和。

你的解决方案是 O(N*N)，因为 sum() 函数也在循环中运行。所以在你每次执行列表推导时，你需要进行 N 步操作，把所有 N 个元素加到两个总和中，而你有 N 次这样的操作。