Космическая сложность (вспомогательная) для длинного кода

Question

Всякий раз, когда мы вычисляем дополнительное пространство, мы не рассматриваем ввод как часть расчета. Допустим, нам нужен алгоритм для печати цифры до эквивалентного слова, как 1, как «Один», 2 как «Два» и т. Д.

Один из способов сделать это - сопоставление каждой цифры с ее эквивалентом слов.

Map<Integer, String> map = new HashMap<>(); 
map.put(1, "One"); 
..... 
map.put(Integer.MAX_VALUE, "Something equivalent"); 

затем есть функция, чтобы вернуть слово. Это будет учитывать наличие O (N) дополнительного пространства для хранения.

Мой вопрос, что если мы напишем функцию как таковой

public printDigit(int n) { 
    switch(n) { 
     case 1: 
      return "One"; 
     ... 
     case Integer.MAX_VALUE: 
      return "Something equivalent"; 
    } 
} 

Обычно, мы не рассмотрим использование кода пространства быть дополнительное пространство? Я не привык к этой логике, поскольку я никогда не сталкивался с ней раньше. Таким образом, мы будем называть этот алгоритм O (1) дополнительным пространством, поскольку у нас нет дополнительной структуры данных для хранения;

Answer 1

Если компилятор решает сохранить коммутационные шкафы в таблице переходов, сложность пространства не будет O(1), так как реализация будет похожа на карту в C++ или hashmap в Java. Вместо этого это будет O(N).

Другие варианты, доступные компилятору, - это выполнять линейный поиск или двоичный поиск в предусмотренных случаях. Во всех этих параметрах было бы обязательно хранить каждый из коммутационных шкафов в какой-либо форме контейнера. Во всех этих случаях сложность пространства снова будет равна O(N).

Прежде всего, предпочтительнее if-else для удобства чтения. Но, используя код map, код может обеспечить краткость и лучшую ремонтопригодность.