Questions sur l'exécution de temps

Question

Quelle est la durée de fonctionnement en big-O notation de:

vector.push_back(item) 

et

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

Answer 1

O (1) (temps amorti, la réaffectation peut se produire) en cas de push_back()

O (n) dans le cas de erase() ie Linéaire sur le n ombre d'éléments effacés (destructeurs) plus le nombre d'éléments après le dernier élément supprimé (en mouvement).

Answer 2

Pour "vector.push_back (item)" son seul O (1). Et "vec.erase (itr)" O (n) car les éléments suivants sont décalés vers le bas. Editer: Si elle pointe au milieu dans le vecteur, c'est comme O (n/2).

Answer 3

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

Un vecteur est une séquence qui permet l'accès aléatoire à des éléments, l'insertion de la constante de temps et l'enlèvement des éléments à la fin, et l'insertion de temps linéaire et l'enlèvement des éléments au début ou à la milieu.