计算从列表中查找给定数字的所有可能总和组合的函数的时间复杂度

Question

我对如何开始计算给定函数的时间复杂度有点困惑，

function func(A, x):
         A.sort()
         result = []
         Mystery(A, x, 0, [], result)
         return result`
function Mystery(A, x, start, p, result):
          if x == 0:
             result.append(p)
             return
          if x < 0:
             return
         for i from start to n - 1:
             Mystery(A, x - A[i], i + 1, p + [A[i]], result)

它给出的结果是一个列表列表，当每个列表加起来等于数字x时，这里A是一个长度为n的列表

我计算了一下，得出 T(n,x) = O(1) + T(n-1, x-A[0]) + T(n-2, x-A[1]) ... T(n-i ，x-A[n-1]）虽然这让我感到困惑，因为我不知道这是正确的方法还是我犯了一个错误

Answer 1

在最坏的情况下𝑥大于所有数组元素的总和。在这种情况下，程序会尝试输入数组的所有子序列。换句话说，所有组合都是在 𝑝 中进行的，其中 𝐴 中的每个数组元素有两种可能性：要么在 𝑝 中，要么不在 𝑝 中。这为我们提供了 2^𝑛 的可能性。所有这些都是在最坏的情况下创建的。 𝑝 的平均大小为 O(𝑛)，这也是创建一个此类版本的 𝑝 的时间复杂度（这发生在每次递归调用的表达式

p + [A[i]]

中）。

所以时间复杂度是 O(𝑛2^𝑛)