Скорость вставки и удаления в ArrayList и LinkedList [дубликат]

15 октября 2019, 00:50

На данный вопрос уже ответили:

Смысл O-нотации 1 ответ

Расскажите про скорость вставки и удаления, не очень понял что такое константное время и что за конструкции O(1), O(n).
Гуглил до этого нашел:

Быстрый доступ к элементам по индексу за время O(1)

Доступ к элементам по значению за линейное время O(n)

Что за быстрый доступ за время O(1) и что такое линейное время O(n) и как это всё измеряется/проверяется?
Заранее спасибо!

Answer 1

Константное время - имеется ввиду, что независимо от того, сколько будет элементов в структуре то при времени выполнения операции 1 секунду, это время останется как для 1000 элементов, так и для миллиона и для миллиарда и т.п.

Линейное время - означает, что чем больше элементов будет в структуре, тем дольше будет выполняться операция. Т.е. время будет множиться в зависимости от количества элементов n*t, где t время, а n количество элементов. Так например если в структуре 10 элементов и операция выполняется за 1 секунду, то для 100 элементов, она будет выполняться за 10 секунд, для 1000 элементов - 100 секунд.