Установите время и скорость сложности

Question

Я очищаю алгоритмы и структуры данных и у меня есть несколько вопросов, а также утверждения, которые я бы хотел проверить.

ArrayList - O (1) (size, get,set, ...), O (n) - операция добавления.
LinkedList - все операции O (1) (включая add ()), за исключением получения n-го элемента, который является O (п).Я предполагаю, что операция size () также выполняется в O (1), верно?

TreeSet - все операции O (lg (N)).Операция size () принимает O (lg (n)), верно?

HashSet - все операции O (1), если применяется правильная хеш-функция.
HashMap - все операции O (1), анологичные HashSet.

Любые дальнейшие объяснения приветствуются.Заранее спасибо.

Answer 1

ArrayList.add() является амортизированным O (1).Если операция не требует изменения размера, это O (1).Если требует изменения размера, это O (n), но затем размер увеличивается так, что некоторое изменение размера не произойдет некоторое время.

Из Javadoc:

Операция добавления выполняется с амортизированным постоянным временем, то есть добавление n элементов требует времени O (n).Все остальные операции выполняются за линейное время (грубо говоря).Постоянный коэффициент ниже по сравнению с таковым для реализации LinkedList.

Документация, как правило, довольно хороша для коллекций Java с точки зрения анализа производительности.

O (1) дляалгоритмы хеширования - это не просто применение «правильной» хеш-функции - даже с очень хорошей хеш-функцией вы все равно можете получить коллизии хеш-функций. обычная сложность равна O (1), но, конечно, это может быть O (n), если все хэши сталкиваются.

(Кроме того, это подсчетстоимость хеширования как O (1) - в действительности, если вы, например, хешируете строки, каждый вызов hashCode может быть O (k) по длине строки.)

Answer 2

Посетите следующие ссылки. Это поможет вам очистить ваши сомнения.

• Структуры данных и их сложность
• Стандартные структуры данных Java Big O нотация