两个看似相似的解决方案在运行时复杂度上的差异

Question

[我试图解决一项任务，并编写了一个解决方案，该解决方案似乎与我开始寻找更有效的解决方案时在网上找到的解决方案非常接近。

这是作业说明

此问题的目标是实现2-SUM的变体算法将在本周的讲座中介绍。

文件包含100万个整数，正负（可能会重复一些！）。这是您的整数数组，文件的第i行指定数组的第i个条目。

您的任务是计算区间内目标值的数量t[-10000,10000]（含），使得在其中存在不同的数字x，y满足x + y = t的输入文件变量all_ints是包含所有整数的列表

hashtable = set(all_ints)
min_t = -1024
max_t = -min_t + 1

solutions = 0
k = 0

from time import time

# Solution 1 that I wrote
t0 = time()
for n in range(min_t, max_t):
    solutions+=1 if any([True if 2*i!=n and n-i in hashtable else False for i in hashtable]) else 0


# Solution 2 that I found online
t1 = time()
solutions2 = sum(1 for n in range(min_t, max_t) if any(n - x in hashtable and 2 * x != n for x in hashtable))
t2 = time()

print(t1-t0) #857.0168697834015
print(t2-t1) #591.8803908824921

根据基本检查，这两种解决方案看起来非常相似。然而，它们的运行时间却大不相同，尽管两者均呈线性比例，但当我减小min_t的值时，它们会进一步偏离。

导致这种情况的两个实现之间的根本区别是什么？>

我正在尝试解决一项任务，并编写了一个解决方案，该解决方案似乎与我开始寻找更有效的解决方案时在网上找到的解决方案非常接近。这是赋值语句The ...

Answer 1

如上所述，如果...则显式执行False。这是附加步骤，如果值较大，则可能会显示一些开销。最重要的是，您首先要构建整个列表，然后检查其中是否有True。第二种解决方案使用了一个惰性的生成器，一旦遇到True值，它将立即停止执行，从而可以节省大量时间。

Answer 2

可能您额外的列表理解创建可能会减慢算法的速度，从而增加额外的容器开销。