循环时间复杂度内的递归

Question

我创建此算法是为了使用回溯策略解决问题。问题在于：

Given a set A of n integers and two integer values, m and c. Calculate all subsets of A, of m elements, that the sum of their values is 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

您的算法的时间复杂度将为 O(m * 2^m)，因为您考虑 A 的所有子集小于或等于 m，因为您考虑 level他们每个人！。乘以m是为了求和每个子集的值。

Answer 2

该算法计算每个子集，假设 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。

循环时间复杂度内的递归

Recursion inside a loop time complexity

algorithm

complexity-theory

time-complexity