c++ - for - little o notation

complejidad del mapa multiset, mapa y hash

Question

Me gustaría saber la complejidad en la notación Big O de las clases de mapas multiset, map y hash de STL cuando:

• insertar entradas
• acceder a las entradas
• recuperar entradas
• comparando entradas

Answer 1

map, set, multimap y multiset

Estos se implementan utilizando un árbol rojo-negro , un tipo de árbol de búsqueda binaria equilibrada . Tienen los siguientes tiempos de ejecución asintótica:

Inserción: O (log n)
Búsqueda: O (log n)
Eliminación: O (log n)

hash_map, hash_set, hash_multimap y hash_multiset

Estos se implementan usando tablas hash . Tienen los siguientes tiempos de ejecución:

Inserción: O (1) esperado, O (n) peor caso
Búsqueda: O (1) esperado, O (n) peor caso
Eliminación: O (1) esperado, O (n) peor caso

Si usa una función hash adecuada, casi nunca verá el peor de los casos, pero es algo a tener en cuenta: consulte este artículo para ver un ejemplo.

Answer 2

Puede encontrar esta información en la documentación de SGI STL: http://www.sgi.com/tech/stl/

Básicamente, tanto multiset como mapas son árboles binarios ordenados, 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 después de 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.

Answer 3

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.