Сложность времени - Копирование записей на карте в Arraylist

Question

Я искал эффективные способы сортировки хеш-карты по его значению, и я наткнулся на решения, которые утверждают, что они 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)?

Это мое понимание: мы перебираем записи на карте (это 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), потому что сортировка будет доминирующей операцией.