python - 了解 python 代码的时间复杂度

Question

我对时间复杂度问题完全陌生。我正在为 Codility 练习编写 Python 代码，我编写的代码返回超时错误，时间复杂度为 O(N*N)。预期时间复杂度为 O(N)。

给定一个整数列表A，我正在尝试计算所有索引 i 的 A[0:i] 总和与 A[i:] 总和之间的最小差异 在 A 中。

这是我的解决方案:

def solution(A):
    # write your code in Python 2.7
    a=[]
    for i in range(1,len(A)):
        a.append(abs(sum(A[0:i])-sum(A[i:len(A)+1])))
    return min(a)

我尝试通过实现以下内容来改进代码

import sys
def solution(A):
    # write your code in Python 2.7
    a=sys.maxint
    for i in range(1,len(A)):
        temp=abs(sum(A[0:i])-sum(A[i:len(A)+1]))
        if temp<a:
            a=temp
    return a

我仍然遇到同样的复杂性。我知道 abs 步骤需要花费大量时间来计算。如何降低这段代码的时间复杂度？有没有直观的方法来看待时间复杂度问题？

Answer 1

在循环的每次迭代中，您重新计算索引 i 之前的元素总和，以及索引i之后的元素之和。这是低效的，因为您可以边走边积累金额。

suffix = sum(A)
prefix = 0
mindiff = suffix

for a in A:
    prefix += a
    suffix -= a
    mindiff = min(mindiff, abs(prefix - suffix))

return mindiff

您的代码还存在其他问题:

• 无需列出差异列表。您可以跟踪最小值(就像我一样)
• A[i:len(A)+1] 中的结束索引超出了 A 的范围，阅读起来比较困惑，建议您可能会对 Python 中的列表索引感到困惑。这应该是 A[i:len(A)]，或者更好，简单地是 A[i:]。

Is there an intuitive way of looking at time complexity problems?

绝对是的。这里的直觉是计算一系列值的总和，你需要迭代它们。这就是 O(N) 。如果这是在另一个 O(N) 循环内，那么整体复杂度就变成了O(N*N)。你的错误是忽视了求和的成本。