将hashmap用作计数器时的空间复杂性

Question

遇到这样的代码：

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

空间复杂度是多少？如果答案是O(1)，那么如果算法是计算8字节流(或16字节32字节等)的唯一出现次数，该怎么办？即问题空间的上限超出了计算机的存储空间。

Answer 1

O(length(str))中问题的空间复杂度。

至于字符串，您将为每个新的字符创建一个新的条目。

现在，在您的情况下需要考虑的事情很少:字符串的长度是否大于由char数据类型定义的总字符集的长度。

如果是，则空间复杂度为O( char数据类型中的总字符数)= O(1)，否则为O(length(str))。

utf-32字符类型也是如此。

现在它完全取决于你的输入是什么-如果输入是巨大的，通常大于char数据类型的总大小或utf-32大小，那么空间复杂度就被认为是恒定的。

Answer 2

2,164,864个“字符”可能由UTF-8编码。

因此，如果所有字符都出现在给定的字符串中，则使用的字节数为2,164,864字节(假设每个字符1个字节)。

因为..。2,164,864也是一个常数。因此，在任何情况下，问题的空间复杂度都保持为O(1)。

O(1)表示恒定的空间。