Сложность пространства, когда hashmap используется как счетчик

Question

Встречайте такой код:

void foo(const string& str) {
  unordered_map<char, unsigned int> m;
  for (char c: str) {
    ++m[c];
  }
}

Какая сложность пространства? если ответ - O (1), то что, если алгоритм должен подсчитать уникальное появление 8-байтового потока (или 16-байтового 32-байтового и т.д. c)? т. е. верхняя граница проблемного пространства определяет размер памяти компьютера.

Answer 1

2 164 864 «символа» потенциально могут быть закодированы с помощью UTF-8.

Итак, если все символы присутствуют в данной строке, то количество используемых байтов составляет 2 164 864 байта (предположим, 1 байт на символ) .

Поскольку ... 2 164 864 также является константой. Таким образом, в любом случае пространственная сложность проблемы остается O (1).

O (1) означает постоянное пространство.

Answer 2

Пространственная сложность вашей проблемы в O (length (str)).

Что касается строки, вы создаете новую запись для каждого нового встречаемого символа.

Теперь их мало вещи, которые следует учитывать в вашем случае: длина строки больше, чем длина всего набора символов, определенного типом данных char.

Если да, то сложность пространства составляет O (общее количество символов в типе данных char) = O (1 ) иначе это O (length (str)).

То же самое и для типа символов utf-32.

Теперь это полностью зависит от ваших входных данных - если входные данные имеют огромные размеры , обычно больше, чем общий размер типа данных char или размер utf-32, сложность пространства считается постоянной.