循环时间复杂度内的递归

Question

我创建了这个算法来使用回溯策略解决问题。问题在于：

给定一个包含 n 个整数和两个整数值 m 和 c 的集合 A.计算 M 个元素的 A 的所有子集，它们的值之和为 c。

算法（在 java 中）：

public class Algorithm {
    private List<Integer> a;
    private int m;
    private int c;
    /**
     * @param a Initial set
     * @param m Maximum number of elements stored in the subset
     * @param c Desired sum
     */
    Algorithm(List<Integer> a, int m, int c) {
        this.m = m;
        this.c = c;
        this.a = a;
        findSubsets(0, new int[m], 0, 0);
    }
    /**
     * @param i Index to go through the initial set
     * @param subset Solution candidate
     * @param level Current number of elements stored in the subset
     * @param sum  Current sum of the elements stored in the subset
     */
    private void findSubsets(int i, int[] subset, int level, int sum) {
        // Base case
        if (level == m) {
            if (sum == c) {
                System.out.println(Arrays.toString(subset));
            }
        }
        // Exploration
        else {
            while (i < a.size()) {
                subset[level] = a.get(i);
                findSubsets(i + 1, subset, level + 1, sum + a.get(i));
                i++;
            }
        }
    }
}

时间复杂度：

通过

这个解决方案，我通过实验确定，当m趋向于n时，复杂度趋向于O（2^n）。但是，在阅读了有关如何计算时间复杂度的指南后，我仍然无法从数学上确定此结果。我对平均情况也非常感兴趣，我对如何计算它感到非常迷茫。

我知道这可能是一个新手问题，但如果有人能帮我一把，我将不胜感激！谢谢

Answer 1

该算法计算每个子集，假设 m=n。对于每个0<=i<n，你把i-1时可能的子集数量加倍，因为每个子集在级别i-1有两种情况使它们达到级别i：添加a[i]，或者不添加。

例如，如果 i=2 并且有 4 个

可能的子集（例如 {}、{A}，{B}，{AB}），那么对于 i=3，将有 4 个不包含 a[3] 的子集（与以前相同），以及 4 个包含a[3]的新子集（例如 {C}、{AC}，{BC}，{ABC}），总共 8 个。

因为我们对每个i<n加倍，在n=m的情况下，可能的子集的总数是2^n。

Answer 2

当您

考虑小于或等于m A的所有子集时，算法的时间复杂度将O(m * 2^m)，因为您为每个子集level进行系数！乘以 m 用于对每个子集的值求和。