对于 hashmap 和列表实现，计算字母出现次数 O(1) 的函数是否额外 space 复杂？
Is the extra space complexity of a function that counts letter occurrences O(1) for both a hashmap and list implementation?
如果你使用散列映射（或 python 中的字典）并为找到的每个字母添加新键/增量键计数 O(n) 或 O(1)？我问是因为 hashmap 的最大大小是 26 个键
另一种解决方案是初始化一个长度为 26 的零数组，并在出现字母时递增对应于字母的索引（例如，如果 a 存在则递增 arr[0]）。据我了解，这样的解决方案需要额外的 O(1) space.
我想最重要的问题是如果一个输入只能有 x 个唯一字符输入，那么额外的 space 是否被认为是 O(1)？
O(N) 中的 N 是数组中元素的数量。由于无论您传入 100 个元素还是 100,000,000 个元素，您的 space 要求都是相同的，因此 space 要求是 O(1)：它不依赖于输入大小。
技术上、python 整数可以无限增长。这意味着您的 space 要求实际上类似于 O(log(N))，因为 O(log_base_256(N)) = O(log(N) / log(256)) = O(log(N))。大多数其他语言都有真正的 O(1) 要求，因为它们限制了整数的大小，无论是 32 位还是 64 位。出于所有实际目的，您可以将整数的大小限制在一个足以描述所有可用内存的值，并将其称为 O(1).
如果你使用散列映射（或 python 中的字典）并为找到的每个字母添加新键/增量键计数 O(n) 或 O(1)？我问是因为 hashmap 的最大大小是 26 个键
另一种解决方案是初始化一个长度为 26 的零数组，并在出现字母时递增对应于字母的索引（例如，如果 a 存在则递增 arr[0]）。据我了解，这样的解决方案需要额外的 O(1) space.
我想最重要的问题是如果一个输入只能有 x 个唯一字符输入，那么额外的 space 是否被认为是 O(1)？
O(N) 中的 N 是数组中元素的数量。由于无论您传入 100 个元素还是 100,000,000 个元素，您的 space 要求都是相同的，因此 space 要求是 O(1)：它不依赖于输入大小。
技术上、python 整数可以无限增长。这意味着您的 space 要求实际上类似于 O(log(N))，因为 O(log_base_256(N)) = O(log(N) / log(256)) = O(log(N))。大多数其他语言都有真正的 O(1) 要求，因为它们限制了整数的大小，无论是 32 位还是 64 位。出于所有实际目的，您可以将整数的大小限制在一个足以描述所有可用内存的值，并将其称为 O(1).