python - 两个总和运行时间 O(n^2) 或 O(n)

Question

对于两个求和问题，在列表中找到相加等于目标的两个数字。

我的解决方案是创建一个字典/哈希表，然后将所有内容存储为(value, index) [注意:对于列表中的重复数字:较高的索引会覆盖较低的索引]

然后再次遍历列表以找到另一个项目。

def twoSum(nums, target): 
    lookup = dict((v, i) for i, v in enumerate(nums))
    for i, v in enumerate(nums):
        if target - v in lookup and i != lookup[target-v]:
            return [lookup[target - v], i]

我认为上述算法需要 O(n * n/2) =，因此需要 O(n^2) 时间，但我看到其他一些人说它只需要线性时间。有人可以证实这一点吗？

Answer 1

该算法需要常数时间，因为操作 target - v in lookup 在常数时间内运行。 for 循环只有一层。

def twoSum(nums, target):
    lookup = dict((v, i) for i, v in enumerate(nums)) # N
    for i, v in enumerate(nums):  # N
        if target - v in lookup and i != lookup[target - v]: # average constant
            return [lookup[target - v], i]  # constant

如果您执行一个 O(N) 操作，然后执行另一个 O(N) 操作，序列仍然是 O(N) .

这里我们只讨论平均时间复杂度。有可能有一个非常糟糕的散列函数和很多冲突，这样 target - v in lookup 实际上需要 O(N) 时间，所以最坏情况下的复杂度实际上是 O(N^2)。但是有了 dict，您就不太可能遇到这种情况。