java - 程序代码的运行时间

Question

我需要你的帮助。请问你能帮帮我吗。

输入：具有 n 个自然数的数组 A。

count = 0
for each subset S of 4 elements of A do:
  sum = "sumFormula" from i = 0 to 3  S[i]
  for i from 0 to n-1 do:
        if sum == A[i]:
            count = count+1
return count.

我不明白。需要什么时间？

我的想法：我认为它具有指数运行时间，因为当我将输入大小加倍时，它是平方的。但我不确定。

标签： javapythonalgorithmparallel-processingsum

Answer 1

算法的很多复杂性是隐藏的。

尤其是：

对于 A 中 4 个元素的每个子集 S

这些子集是如何确定的？
具有 n 个元素的集合有 2^n 个可能的子集。简单地说，第一步可能是指数运行时间的原因。

该算法的其余部分本质上是计算每个子集的总和。这不会对运行时产生太大影响。