Me gustaría saber la complejidad en Big O notación del conjunto múltiple STL, el mapa y clases de mapa hash cuando:conjunto múltiple, mapa y mapa hash complejidad
puede encontrar esta información en la documentación de SGI STL: http://www.sgi.com/tech/stl/
Básicamente, tanto multiset como mapas están ordenados árboles binarios, por lo que insertar/encontrar 1 de N entradas toma O (log N). Ver Assoc ordenado Contenedores en la documentación.
Obviamente, la gran ventaja de Hashmap es O (1) para insertar y encontrar entradas.
Acceder a él una vez encontrado es O (1) para todas las estructuras. Comparación, ¿qué quieres decir con eso? Suena como O (1) para mí, después de todo se encontraron.
Estos se implementan utilizando un red-black tree, un tipo de balanced binary search tree. Tienen las siguientes veces asintóticas de ejecución:
Inserción: O (log n)
Lookup: O (log n)
Supresión: O (log n)
Estos se implementan usando hash tables. Tienen las siguientes tiempos de ejecución:
Inserción: O (1) que se espera, O (n) peor de los casos
Lookup: O (1) que se espera, O (n) peor de los casos
Supresión: O (1) que se espera, O (n) el peor caso
Si utiliza una función hash adecuada, casi nunca verá el peor comportamiento posible, pero es algo a tener en cuenta; consulte this paper para ver un ejemplo.
¿Todo lo que dices en 'hash_ *' se refiere a C++ 11 desordenado y Boost.Unordered contenedores? – myWallJSON
@myWallJSON: sí – sehe
Las plantillas de clase 'hash_ *' son parte de [Silicon Graphics STL] (https://www.sgi.com/tech/stl/). Estos se incorporaron a la revisión de C++ 11 con los nombres 'unordered_ *' (unordered_map, unordered_set, etc.). Además, se han incluido en bibliotecas libstdC++, Visual C++ y Boost C++. – soliosg
cppreference.com es donde voy para mis preguntas de referencia de C++. Ellos hacen un muy buen trabajo de delinear la notación Big O para la mayoría de las funciones sobre las que preguntaste anteriormente.
esto es en realidad mi publicación y no puedo entender por qué aparezco inactivo y por lo tanto no puedo cambiarlo ... – Harry