java - 返回值是否考虑了空间复杂度

Question

下面是一个用于生成多个集合的算法。准确地说，它解决了以下问题 打印数组中元素的所有组合，使得数组的第一个元素是 d 并且 数组中的下一个元素可以是数组中前一个元素的 +1 或 -1。代码是必需的。 输入:num=4，level=3。输出 - 4、3、2 || 4, 3, 4 || 4, 5, 4 || 4、5、6。

这个问题不使用 int[] arr = new int[level] 作为最终被复制到 int 数组列表中的数据存储。

下面代码的空间复杂度是多少？是 O(level) 即用于解决问题的存储还是 O(2^level - 1) 即返回类型的大小？

public static List<int[]> getCombinations(int num, int level) {
        final List<int[]> combinations = new ArrayList<int[]>();
        int[] arr = new int[level]; 
        computeCombinations(num, level - 1, 0, combinations, arr);  // note : its level - 1, since currentlevel is set to 0.
        return combinations;
    }


    private static void computeCombinations(int num, int level, int currLevel, List<int[]> list, int[] arr) {
        arr[currLevel] = num;

        if (currLevel == level) {
            // list.add(arr);  <- wrong to do it so
            int[] temp = new int[arr.length];
            System.arraycopy(arr, 0, temp, 0, arr.length);
            list.add(temp);
            return;
        }

        computeCombinations(num - 1, level, currLevel + 1, list, arr);
        computeCombinations(num + 1, level, currLevel + 1, list, arr);
    }

Answer 1

空间复杂度考虑了算法使用的实时内存量，因此 ArrayList<int[]>复杂性的因素。但是，帖子顶部给出的算法描述说您只需要打印组合，而不是返回它们；如果您在创建组合后立即打印出它们然后丢弃它们(即破坏性地更新组合而不是复制它)，那么您将提高空间复杂度。