Вопросы о времени выполнения

Question

Что такое время выполнения в big-O нотации из:

vector.push_back(item)

и

vec.erase(itr)  // itr points in the middle of a vector

Answer 1

O (1) (амортизированное время, может произойти перераспределение) в случае push_back()

O (n) в случае erase() т.е. Линейный по количеству удаленных элементов (деструкторов) плюс количество элементов после последнего удаленного элемента (перемещение).

Answer 2

С http://www.sgi.com/tech/stl/Vector.html:

Вектор - это последовательность, которая поддерживает произвольный доступ к элементам, постоянное время вставки и удаления элементов в конце, а также линейное время вставки и удаления элементов в началеили в середине.

Answer 3

Для "vector.push_back (item)" это только O (1). И "vec.erase (itr)" O (n), потому что более поздние элементы смещены вниз.

Редактировать: если он указывает на середину в векторе, это похоже на O (n / 2).