Сложность времени цикла по ArrayList и размещения значений в HashMap по сравнению с простым поиском ArrayList

Question

Если вы начнете с ArrayList<Obj>, есть ли выигрыш во времени для цикла по ArrayList и помещения значений в HashMap с полезным ключом для поиска? Или зацикливание ArrayList в значительной степени сводит на нет все преимущества, которые вы получили бы, поместив его в HashMap?

Полагаю, вы все равно получили бы выгоду, если бы собирались выполнить много поисков на новом HashMap, но как быть с одним поиском?

Answer 1

Только для одного поиска нет смысла создавать HashMap, так как время, необходимое для построения HashMap, будет линейным (O(n)), то есть то же самое время, которое требуется для прямого поиска * 1004. *.

Поскольку создание HashMap имеет некоторые накладные расходы, превышающие время, необходимое для итерации по ArrayList, один поиск с прямой итерацией по ArrayList должен быть быстрее, чем сборка HashMap, а затем поиск некоторый ключ (хотя асимптотически обе операции должны занимать одно и то же время).

A HashMap оправдано, если вы собираетесь использовать его несколько раз. Например, если вы выполните поиск n на ArrayList размера n, это займет O(n^2) время (поскольку каждый поиск потребует O(n) времени).

С другой стороны, если вы поместите элементы ArrayList в Map и выполните n поиск на Map, время выполнения будет O(n) (поскольку каждый поиск будет выполняться ожидаемым постоянное время).