python - 更快地替代嵌套 for 循环时间

Question

我需要计算/从由以下组成的可能整数列表中

i + 2j + k，其中 1 <= i,j,k <= N。

我知道这将是从 4 到 4N 的所有整数，但我也需要它们的频率，因此必须制定一个列表。我也找不到频率的模式。我的蛮力方法是：

对于 n = 2，列表将类似于：[4,5,6,5,7,6,7,8]

for i in range(N+1):
  for j in range(N+1):
     for k in range(N+1):
         #creating a list

否则有模式吗？就像如果i + 2j + k = P，P的频率= P形式的某个方程。据我尝试，没有找到任何线性或二次方程。

它的复杂性是 O^3，所以我需要一个更好的版本/替代品。我对想法持开放态度。如果您有什么不明白的地方，请询问。

标签： pythonalgorithmtime-complexity

Answer 1

由于 noboding 发布了一个线性解决方案（我相信有一个），我将发布一个二次解决方案：

def ways(n,N):
    s=0
    s1 = 0
    s2 = 0


    for j in range(1,N+1):
        if n - 2*j < 2:
            break
        if n - 2*j > 2*N:
            continue
        s1+= min(n-2*j - 1,N) +1
        s2+= max(n-2*j-N, 1)

    return s1 - s2


N=2
print({ i: ways(i,N) for i in range(4, 4*N+1) })

输出：

{4: 1, 5: 2, 6: 2, 7: 2, 8: 1}

至少从 O(N^3) 到 O(N^2) 的改进。