¿Cuán eficiente es la función find() en la clase std :: map? ¿Se repite a través de todos los elementos buscando la clave de modo que sea O (n), o esté en un árbol equilibrado, o use una función de hash o qué?Complejidad del tiempo de find() en std :: map?
Log(n) Se basa en un árbol negro rojo.
Editar: n es, por supuesto, el número de miembros en el mapa.
Aunque esto es cierto hasta cierto punto, hay una limitación en los mapas más grandes. Si está buscando conjuntos de datos muy grandes, le recomendaría también buscar contenedores de matriz asociativa alternativos. –
Verdadero es log (n). No es cierto, se basa en árboles rojos/negros. El estándar define la operación para tener una complejidad máxima de log (n) y la forma más efectiva de lograr esto es usar árboles rojos/negros (aunque esto no es un requisito). Por lo tanto, tienes tu carrito antes que el caballo. –
@OrgnlDave: Siempre es cierto (no en cierta medida). –
No itera todos los elementos, realiza una búsqueda binaria (que es O (log (n))). Utiliza el operador < o un comparador para hacer la búsqueda.
Si desea un mapa hash, puede usar std :: unordered_map (agregado en C++ - 0x), que usa una función hash y en promedio (dependiendo de la función hash y los datos que proporcione) find() ser O (1).
@NicolBolas: Recuerdo haber leído en alguna parte que no era obligatorio tener un árbol, gracias por tu comentario. Se arregló mi anwer. – fbafelipe
std::map y std::set son implementados por proveedores de compiladores que utilizan árboles de búsqueda binaria muy equilibrados (por ejemplo, árbol rojo-negro, árbol AVL).
Como señaló correctamente David, find tomaría el tiempo O (log n), donde n es el número de elementos en el contenedor.
Pero eso es con los tipos de datos primitivos como int, long, char, double etc., no con cuerdas.
Si std:string, digamos de tamaño 'M', se utiliza como clave, que atraviesa la altura del árbol binario de búsqueda equilibrado requerirá log n comparaciones de la clave dada con una entrada del árbol.
Cuando std::string es la clave de los std::map o std::set, find y insert operaciones costará O (m log n), donde m es la longitud de cadena dada que debe ser encontrado.
Iba a votar esto por señalar que las comparaciones individuales no son necesariamente O (1). Pero luego hiciste la edición sobre Java, que no entiendo. La clave hash devuelta por 'hashCode()' no es un identificador único, por lo que aún necesita hacer una comparación de cadenas O (m) cuando compara dos claves. – jogojapan
Además, generar el hashcode sigue siendo O (m), por lo que no solo no es más rápido, sino que los hashcodes serían _slower_ (suponiendo que no estén en caché) –
@jogojapan Gracias por señalar java.lang.String.hashCode (), corrigió mi respuesta eliminando la parte de javaj y aferrándose a la pregunta que se le hacía. También planteó una [pregunta] (http://stackoverflow.com/questions/17569651/are-string-hashcode-in-java-pre-computed) –
Hay documentación para STL, y generalmente indica complejidad. http://www.cplusplus.com/reference/stl/map/find/ –
Ver: [¿Cuáles son las garantías de complejidad de los contenedores estándar] (http://stackoverflow.com/q/181693/14065) –