algorithm - 文件中单词的出现次数 - 复杂性？

Question

鉴于我有一个文件，其中包含一组单词：

1）如果我选择一个哈希表来存储单词->计数，那么查找特定单词出现的时间复杂度是多少？

2）我怎样才能按字母顺序返回这些单词？

如果我选择哈希表，我知道 1) 的时间复杂度将是 O(n) 来解析所有单词，而 O(1) 来获取特定单词的计数。

我看不到如何订购哈希表以及时间复杂度是多少。有什么帮助吗？

Answer 1

可排序的哈希映射本质上变成了二叉树。在 java 中，您可以看到 TreeMap 在查找和插入时使用 O(log n) 实现 SortableMap 接口。

如果您想要最佳的理论性能，您可以使用带有 O(1) 查找和插入的 HashMap，然后使用带有 O(n) 的桶/基数排序进行显示/迭代。

实际上，对字符串使用基数排序会比快速排序 O(n log n) 执行得更差。

Answer 2

使用哈希表有两个缺点 1- 它们不以排序方式存储数据，2- 哈希值的计算通常很耗时。在最坏的情况下，它们还具有插入/删除/查找的线性复杂性。

我的建议是使用Trie来存储您的单词。插入/查找有保证的 O(1)（字数）。对 Trie 的预排序遍历将给出 Trie 中单词的排序列表。

Answer 3

你对（1）的分析是正确的。

大多数哈希表实现（我知道）没有隐式排序。

要获得有序列表，您必须对列表进行排序 ( O(n log n))，对列表的查询需要O(log n).

从理论上讲，您可以定义一个哈希操作和排序的实现，但是使其分布良好（为了提高效率）将很困难，而仅排序会简单得多。

如果它是一个包含大量重复项的文件，最好的想法可能是首先使用散列来消除重复项，然后遍历哈希表以获取非重复项列表并对其进行排序。