将hashmap用作计数器时的空间复杂性
将hashmap用作计数器时的空间复杂性
提问于 2020-08-06 16:06:06
遇到这样的代码：
void foo(const string& str) {
unordered_map<char, unsigned int> m;
for (char c: str) {
++m[c];
}
}空间复杂度是多少？如果答案是O(1)，那么如果算法是计算8字节流(或16字节32字节等)的唯一出现次数，该怎么办？即问题空间的上限超出了计算机的存储空间。
回答 2
Stack Overflow用户
发布于 2020-08-06 16:10:36
O(length(str))中问题的空间复杂度。
至于字符串，您将为每个新的字符创建一个新的条目。
现在，在您的情况下需要考虑的事情很少:字符串的长度是否大于由char数据类型定义的总字符集的长度。
如果是，则空间复杂度为O( char数据类型中的总字符数)= O(1)，否则为O(length(str))。
utf-32字符类型也是如此。
现在它完全取决于你的输入是什么-如果输入是巨大的，通常大于char数据类型的总大小或utf-32大小，那么空间复杂度就被认为是恒定的。
Stack Overflow用户
发布于 2020-08-06 16:13:41
2,164,864个“字符”可能由UTF-8编码。
因此，如果所有字符都出现在给定的字符串中，则使用的字节数为2,164,864字节(假设每个字符1个字节)。
因为..。2,164,864也是一个常数。因此，在任何情况下，问题的空间复杂度都保持为O(1)。
O(1)表示恒定的空间。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/63287635
复制相关文章
相似问题
Javascript:在JS文件中加载外部JS文件
在中通过jQuery $ajax加载js文件
在我的javascript中加载JQuery.js
Javascript:在JS文件中加载javascript依赖项
有没有同步加载JS文件的JavaScript或jQuery方法？
添加站长 进交流群
领取专属 10元无门槛券
AI混元助手 在线答疑
关注 腾讯云开发者公众号
洞察 腾讯核心技术
剖析业界实践案例
腾讯云开发者
