Учитывает ли возвращаемая стоимость для сложности пространства

Question

Ниже приведен алгоритм, который используется для создания нескольких наборов. Именно он решает следующий вопрос: Print all combination of element in the array such that first element of array is d and next element in the array can be +1 or -1 the previous element in the array. Code was required. Input: num=4, level=3. Output - 4, 3, 2 || 4, 3, 4 || 4, 5, 4 || 4, 5, 6.

Этот вопрос не использует int[] arr = new int[level] как хранилище данных, которое в конечном итоге копируется в список массивов int.

Какова космическая сложность следующего кода? Это O (уровень), то есть хранилище, используемое для решения проблемы, или это O (2^уровень - 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[]> факторов сложности. Однако описание алгоритма, приведенное в верхней части вашего сообщения, говорит, что вам нужно только распечатать комбинации, а не возвращать их; если вы сразу же распечатываете свои комбинации после их создания и затем отбрасываете их (т. е. разрушаете комбинацию, а не копируете ее), тогда вы улучшите свою пространственную сложность.