Je voudrais connaître la complexité de Big notation O du TSL multiset, la carte et les classes de carte de hachage lorsque:multiset, carte et carte de hachage complexité
Vous pouvez trouver ces informations dans la documentation SGI STL: Fondamentalement, le multiset et les cartes sont des arbres binaires triés, donc insérer/trouver 1 sur N entrées prend O (log N). Voir Assoc. Triée. Conteneurs dans la documentation.
De toute évidence, le grand avantage de Hashmap est O (1) pour l'insertion et la recherche d'entrées.
L'accès après trouvé est O (1) pour toutes les structures. Comparaison, que voulez-vous dire par là? On dirait O (1) pour moi, après tout ont été trouvés.
Ceux-ci sont mis en œuvre au moyen d'un red-black tree, un type de balanced binary search tree. Ils ont les asymptotiques temps d'exécution suivantes:
Insertion: O (log n)
Recherche: O (log n)
Suppression: O (log n)
Ils sont implémentés en utilisant hash tables. Ils ont les runtimes suivants:
d'insertion: O (1) prévu, O (n) pire des cas
Recherche: O (1) prévu, O (n) pire des cas
Suppression: O (1) prévu, O (n) pire cas
Si vous utilisez une fonction de hachage appropriée, vous ne verrez presque jamais le pire des cas, mais c'est quelque chose à garder à l'esprit - voir this paper pour un exemple.
Est-ce que tout ce que vous dites sur 'hash_ *' se réfère aux conteneurs C++ 11 non ordonnés et Boost.Unordered? – myWallJSON
@myWallJSON: yes – sehe
Les modèles de classe 'hash_ *' font partie de [STL Silicon Graphics] (https://www.sgi.com/tech/stl/). Ils ont été incorporés dans la révision C++ 11 sous les noms 'unordered_ *' (unordered_map, unordered_set, etc.). Ils ont également été inclus dans les bibliothèques libstdC++, Visual C++ et Boost C++. – soliosg
cppreference.com est où je vais pour mes questions de référence C++. Ils font un très bon travail de décrivant la notation Big O pour la plupart des fonctions que vous avez posées ci-dessus.
c'est en fait mon message et je ne comprends pas pourquoi je semble inactif et ne peux donc pas le changer ... – Harry