Космическая сложность HashMap при итерации по массиву в линейном времени

У меня есть сомнения относительно пространственной сложности программы. Предположим, что я повторяю Array (сохраняет идентификаторы событий) размером n (может быть в миллиардах). Я хотел отслеживать появление каждого идентификатора события, поэтому я использовал хэш-карту для хранения идентификатора события как ключа и его счетчика в качестве значения.Космическая сложность HashMap при итерации по массиву в линейном времени

Вот псевдо-код:

Map m = HashMap<> 
for i to n-1 
    if m.contains(i) 
    int prevCount = m.get(i) 
    m.put(i, prevCount +1) 
    else 
    m.put(i, 1)

Что бы пространство сложность?

PS Это мой первый вопрос в stackoverflow, если он кажется дублирующим, пожалуйста, направить меня к правильному ответу.

источник

2014-12-06 here4learn

Ваша петля добавляет не более пары ключей/значений n-1 к HashMap.

Следовательно, сложность пространства O(n), так как HashMap внутренняя память состоит из массива, размер которого будет достигать мощности 2 близко к п (предполагается, что вы не давали начальную емкость HashMap, что значительно больше, чем n), и каждый элемент массива является связанным списком с средним числом элементов O(1).

источник

2014-12-06 17:52:53 Eran

Спасибо за ваш ответ, поэтому, когда мы вычисляем пространственную сложность специально для структуры данных типа хэш-карты, рассмотрим пространство, взятое каждым К, V или рассмотрим Пространство, взятое объектом-объектом в массиве. Допустим, моя память программ может хранить до миллиарда элементов, и я получил такое же количество событий, что и все уникальные, если мы рассмотрим сложность пространства для каждого K, V, это будет n^2 элемента в памяти, которые могут выйти из памяти. Я немного запутался здесь. Извините, мой вопрос может звучать как новичок, но, пожалуйста, дайте свои материалы. – here4learn

@ here4learn обычно вы можете считать пространство, взятое одной парой значений ключа, постоянным, поэтому сложность пространства карты зависит только от общего числа пар. – Eran

Спасибо @Eran за ваше время. – here4learn

Космическая сложность HashMap при итерации по массиву в линейном времени

ответ

Смежные вопросы