Расчет сложности с помощью stl vector?

Question

Я пытаюсь рассчитать сложность некоторых алгоритмов, но я не знаю, как измерить сложность операций с векторами. Например, какова сложность push_back()?

ссылка

В C++ я нашел «Constant (амортизируется время, перераспределение может произойти). Если перераспределение происходит, перераспределение сам до линейного во всем размере.»

Что это значит? Является ли операция сложности O (n)? (n - длина вектора).

спасибо.

Answer 1

Сложности для вектора:

• push_back: O (1).
  Амортизированный стенд для «округлых», поскольку эта сложность зависит от возможного перераспределения.

Вы перераспределению когда размер вектора больше:

size_type capacity() const; 

Returns: Общее количество элементов, что вектор может содержать без , требующих перераспределения.
Примечания: Reallocation аннулирует все ссылки, указатели и итераторы , ссылаясь на элементы в последовательности . Гарантируется, что перераспределение не происходит во время вставок , которые происходят после вызова резервирования() до момента, когда вставка сделает размер вектора большим, чем размер , указанный в последнем вызове reserve().