java - 时间复杂度 - 将映射条目复制到 Arraylist

Question

我一直在寻找根据值对 HashMap 进行排序的有效方法，我遇到了声称是 O(n log n) 的解决方案，方法是将条目复制到列表并按值对列表进行排序；复制回 LinkedHashMap。我在想这可能是 O(n^2) 而不是 O(n log n)。

List<Entry<K, V>> entries = new ArrayList<Entry<K, V>>(map.entrySet());

我想确认一下上面代码的时间复杂度是不是O(n^2)？

这是我的理解:我们通过 map 的条目进行迭代(这是 O(n))，当我们将每个条目添加到列表时，它会被添加到列表的末尾和执行所需的时间这将是 O(n) 以及使其成为 O(n^2)。

这是正确的吗？

Answer 1

1. 执行 new ArrayList<Entry<K, V>>(map.entrySet())是 O(n)。 map.entrySet()将转换为 Entry[]与 toArray() .没有通常的追加和调整大小 add() .

2. 排序 ArrayList是 O(n log n) 由于 TimSort .

3. 创建 new LinedHashMap来自 ArrayList是 O(n)。

整个方法将是 O(n log n)，因为排序将是主要操作。