Пространство сложности в двух сумм

Question

я написал кусок кода из двух сумм:

public static int[] twoSums0(int[] nums, int target){ 

    for(int i=0;i<nums.length;i++){ 
     for(int j=i+1;j<nums.length;j++){ 
      if(nums[i] == target-nums[j]){ 
       return new int[]{i,j}; 
      } 
     } 
    } 
    throw new IllegalArgumentException("No solution"); 
} 

Я просто хочу знать, почему сложность пространства O (1)? И почему, когда мы используем hashmap, он становится O (n)?

Сложность времени очень проста для понимания, но я не получаю сложность пространства.

Answer 1

Чтобы вычислить сложность пространства, вам необходимо проанализировать асимптотический размер всех объектов и примитивов, созданных вашим методом. Вы не указываете размер ввода.

Этот метод создает не более одного массива из 2 элементов (в дополнение к двум примитивам, используемым для индексов циклов). Поэтому для этого требуется постоянное пространство (т. Е. Сложность пространства O(1)).

Если вы будете использовать HashMap улучшить временную сложность этого метода, я предполагаю, что вы будете добавлять все элементы входного массива, что HashMap, что потребует O(n) пространства.