J'ai une carte d'int à un vecteur,
map<int,vector<int>> m
Supposons que je mappe N éléments à x.
Maintenant, quand j'écris, vecteur v = m [x]
Quelle est la complexité temporelle de la cartographie d'un vecteur. Est-ce O (1) à cause des itérateurs ou O (N)!
3 Réponses :
Abstraire une valeur d'un std :: map est O (log N).
Notez qu'en plus de cela, vous prenez une copie de valeur de la map valeur, peut-être
const vector& v = m[x];
serait mieux?
Yepp. Mentionné dans la doc. std :: map :: operator [] : Logarithmique dans la taille du conteneur.
Et si j'utilise unordered_map? Sera-ce O (1)!
std :: map est un arbre binaire. En tant que tel, une recherche d'élément unique est de complexité O (log N).
Mais en plus de cela, dans votre cas, la copie vector aura lieu, ce qui est de complexité O (N).
Cependant, le N dans la première expression est le nombre de clés dans la carte, et n'est pas le même N de la seconde expression, où il représente la taille de la valeur .
En supposant que les deux N sont de la même grandeur, la complexité globale serait O (N * logN).
O (logN) pour trouver la clé et O (N) pour copier le vecteur, mais la complexité temporelle réelle serait de nature asymptotique et devrait être bien meilleure que O (NlogN) en termes de performances.
Par conséquent, la complexité temporelle est Big-Oh (NlogN).
Vous pouvez trouver la réponse ici .