Depende de si desea implementar un conjunto ordenado de objetos o un conjunto desordenado de objetos.
Un conjunto es una estructura de recopilación de datos que almacena ciertos valores de manera que los valores no se repiten. Dependiendo de si estos valores se almacenan en un orden o no, el conjunto se denomina conjunto ordenado o conjunto no ordenado. Es una implementación del concepto matemático de conjunto finito.
Implementación básica solo para tener una idea (no se recomienda para ningún caso de uso real)
- ¿Cuáles son algunas de las preguntas famosas al calcular los caminos más cortos (gráficos) usando Dijkstra's, DAG y Bellman-Ford?
- Cómo determinar si un conjunto dado se puede dividir en dos subconjuntos o más de modo que la suma de los elementos en esos subconjuntos sea la misma
- ¿Existen tipos de programas de software que involucren matemáticas, pero que puedan resolver problemas cotidianos (es decir, no un motor de juego de física completo o un nuevo algoritmo criptográfico)?
- ¿Qué es un promedio móvil y, algorítmicamente, cómo se calcula dicho conjunto?
- Cómo mantener una matriz, admitir inserción y asignación aleatorias, y consultar el kth elemento más grande en un intervalo dado
Puede usar una matriz dinámica (ampliable) o una lista vinculada e insertar un nuevo objeto al final si aún no está disponible. El costo de inserción, eliminación y búsqueda de un elemento para dicho conjunto es O (N) tanto en el promedio como en el peor de los casos. Esta es una implicación de conjunto desordenada y la idea se amplía en hash set para que sea utilizable para resolver problemas de la vida real.
+ Extremadamente fácil de implementar
– El tiempo de acceso es muy alto, por lo que no se puede utilizar en la mayoría de los escenarios del mundo real.
Conjunto ordenado
Debido a que almacena los objetos en orden, puede encontrar si un objeto ya existe o no usando divide y vencerás en el tiempo O (log N). Dichos conjuntos se pueden implementar utilizando un árbol de búsqueda binaria autoequilibrado, por ejemplo, árbol Rojo-negro o Treap. Se recomienda el primero porque garantiza que el árbol tenga una altura equilibrada.
El costo de inserción, eliminación y búsqueda de un elemento para dicho conjunto es O (Log N) tanto en el promedio como en el peor de los casos.
+ Compacto (en comparación con otra implementación de conjunto)
+ Puede recorrer el conjunto para obtener contenidos en orden ordenado.
– La complejidad del tiempo de acceso es O (log N)
Conjunto desordenado (también conocido como conjuntos de hash)
Como dice el otro nombre, generalmente se implementan (casi siempre) como tablas hash. Si se utilizan buenas funciones hash y el tamaño de la tabla es correcto (factor de carga), puede esperar un tiempo O (1) para la inserción, eliminación y búsqueda de un elemento. Por lo general, se implementa tomando una matriz (llamada tabla hash) donde cada elemento es una lista vinculada para resolver colisiones.
+ El tiempo de acceso es rápido O (1) para el caso promedio
+ Es más fácil agregar seguridad de hilo en comparación con el conjunto de árboles discutido anteriormente
– No se garantiza el tiempo de búsqueda O (1). En el peor de los casos, puede ser tan peor como O (N)
– No compacto. es decir, el factor de carga casi nunca es 1.
Puede ampliar la idea para multiset (Permitir múltiples registros con el mismo valor clave)
