关于 Hash Map 与 Trie 时间复杂度的混淆
Confusion about Hash Map vs Trie time complexity
假设我们正在比较 hashmap 和 trie 中搜索函数的时间复杂度。
在我能找到的很多资源中，时间复杂度被描述为
哈希图得到：O(1)
对比
Trie 搜索：O(k)，其中 k 是您要搜索的字符串中字符的长度。
但是，我觉得这有点令人困惑。在我看来，样本大小“n”在两种情况下的定义不同。
如果我们将 n 定义为字符数，从而对随着字符数增长到无穷大该算法的复杂性感兴趣，那么 hashmap get 的时间复杂度是否也为 O(k)由于它的哈希函数？
另一方面，如果我们将n定义为数据结构中的词数，那么Trie搜索的时间复杂度不也是O(1)吗，因为词的搜索不依赖于已经存储在 Trie 中的单词数？
最后，如果我们对时间复杂度进行比较，在我看来，Hashmap get 和 Trie 搜索的时间复杂度是一样的。
我在这里错过了什么？
是的，你完全正确。
您缺少的是关于算法复杂性的陈述可以基于您喜欢的任何输入项。在校外，这样的陈述是为了交流，你可以让它们交流任何你想要的。
不过，确保您被理解很重要，因此如果有可能混淆 O(n) 中的 n 是如何测量的，或者任何假设输入的约束（如有界字符串大小），那么你应该明确指定。
假设我们正在比较 hashmap 和 trie 中搜索函数的时间复杂度。
在我能找到的很多资源中，时间复杂度被描述为 哈希图得到：O(1) 对比 Trie 搜索：O(k)，其中 k 是您要搜索的字符串中字符的长度。
但是，我觉得这有点令人困惑。在我看来，样本大小“n”在两种情况下的定义不同。
如果我们将 n 定义为字符数，从而对随着字符数增长到无穷大该算法的复杂性感兴趣，那么 hashmap get 的时间复杂度是否也为 O(k)由于它的哈希函数？
另一方面，如果我们将n定义为数据结构中的词数，那么Trie搜索的时间复杂度不也是O(1)吗，因为词的搜索不依赖于已经存储在 Trie 中的单词数？
最后，如果我们对时间复杂度进行比较，在我看来，Hashmap get 和 Trie 搜索的时间复杂度是一样的。
我在这里错过了什么？
是的，你完全正确。
您缺少的是关于算法复杂性的陈述可以基于您喜欢的任何输入项。在校外，这样的陈述是为了交流，你可以让它们交流任何你想要的。
不过，确保您被理解很重要，因此如果有可能混淆 O(n) 中的 n 是如何测量的，或者任何假设输入的约束（如有界字符串大小），那么你应该明确指定。