Hispanopedia Wiki
Articulo de referencia

Comparación de estructuras de datos

Esta es una comparación del rendimiento de estructuras de datos destacadas , medida según la complejidad de sus operaciones lógicas. Para obtener una lista más completa de estru...

Hispanopedia WikiContenido en espanolLectura gratuita

Esta es una comparación del rendimiento de estructuras de datos destacadas , medida según la complejidad de sus operaciones lógicas. Para obtener una lista más completa de estructuras de datos, consulte la Lista de estructuras de datos .

Las comparaciones en este artículo están organizadas por tipo de dato abstracto . Dado que una única estructura de datos concreta puede utilizarse para implementar muchos tipos de datos abstractos, algunas estructuras de datos pueden aparecer en varias comparaciones (por ejemplo, un mapa hash puede utilizarse para implementar un array asociativo o un conjunto ).

Liza

Una lista o secuencia es un tipo de dato abstracto que representa un número finito de valores ordenados , donde el mismo valor puede aparecer más de una vez. Las listas generalmente admiten las siguientes operaciones:

  • peek : accede al elemento en un índice determinado.
  • insert : inserta un nuevo elemento en un índice dado. Cuando el índice es cero, esto se llama anteponer ; cuando el índice es el último índice de la lista, se llama añadir .
  • eliminar : elimina el elemento en un índice determinado.

Mapas

Los mapas almacenan una colección de pares (clave, valor), de modo que cada clave posible aparece como máximo una vez en la colección. Generalmente admiten tres operaciones: [ 3 ]

  • Insertar : agrega un nuevo par (clave, valor) a la colección, asignando la clave a su nuevo valor. Cualquier asignación existente se sobrescribe. Los argumentos de esta operación son la clave y el valor.
  • Eliminar : elimina un par (clave, valor) de la colección, desvinculando una clave dada de su valor. El argumento de esta operación es la clave.
  • Búsqueda : encuentra el valor (si lo hay) asociado a una clave determinada. El argumento de esta operación es la clave, y el valor se devuelve como resultado de la operación.

Salvo que se indique lo contrario, todas las estructuras de datos de esta tabla requieren un espacio de O( n ).

Claves enteras

Algunas estructuras de datos de mapas ofrecen un rendimiento superior en el caso de claves enteras . En la siguiente tabla, sea m el número de bits de las claves.

Colas de prioridad

Una cola de prioridad es un tipo de dato abstracto similar a una cola o pila convencional . Cada elemento de una cola de prioridad tiene una prioridad asociada. En una cola de prioridad, los elementos con alta prioridad se procesan antes que los de baja prioridad. Las colas de prioridad admiten las siguientes operaciones:

  • insertar : agrega un elemento a la cola con una prioridad asociada.
  • find-max : devuelve el elemento de la cola que tiene la prioridad más alta.
  • delete-max : elimina de la cola el elemento que tenga la prioridad más alta.

Las colas de prioridad se implementan frecuentemente utilizando montículos .

Muchísimo

Un montón (máximo) es una estructura de datos basada en árboles que satisface la propiedad de montón : para cualquier nodo C dado, si P es un nodo padre de C, entonces la clave (el valor ) de P es mayor o igual que la clave de C.

Además de las operaciones de una cola de prioridad abstracta, la siguiente tabla enumera la complejidad de dos operaciones lógicas adicionales:

  • increase-key : actualizando una clave.
  • fusionar : unir dos montones para formar un nuevo montón válido que contenga todos los elementos de ambos, destruyendo los montones originales.

Aquí se muestran las complejidades temporales [ 5 ] de diversas estructuras de datos de montículo. La abreviatura am. indica que la complejidad dada está amortizada; de lo contrario, se trata de la complejidad en el peor de los casos. Para conocer el significado de " O ( f )" y " Θ ( f )", consulte la notación Big O. Los nombres de las operaciones presuponen un montículo máximo.

  1. 1 2 3 Tiempo amortizado.
  2. ↑ make-heap es la operación de construir un montón a partir de una secuencia de n elementos no ordenados. Se puede realizar entiempo Θ ( n ) siempre que meld se ejecute en tiempo O (log n ) (donde ambas complejidades se pueden amortizar). [ 6 ] [ 7 ] Otro algoritmo alcanza Θ ( n ) para montones binarios. [ 8 ] 
  3. 1 2 3 Paramontículos persistentes (que no admiten increase-key ), una transformación genérica reduce el costo de meld al de insert , mientras que el nuevo costo de delete-max es la suma de los costos antiguos de delete-max y meld . [ 11 ] Aquí, hace que meld se ejecute en tiempo Θ (1) (amortizado, si el costo de insert lo es) mientras que delete-max todavía se ejecuta en O (log n ). Aplicado a montículos binomiales asimétricos, produce colas de Brodal-Okasaki, montículos persistentes con complejidades óptimas en el peor de los casos. [ 10 ] 
  4. ↑ Límite inferior deΩ(registro⁡registro⁡norte),{\displaystyle \Omega (\log \log n),}[ 14 ] límite superior deO(22registro⁡registro⁡norte).{\displaystyle O(2^{2{\sqrt {\log \log n}}}).}[ 15 ]
  5. Las colas de Brodal y los montículos de Fibonacci estrictos alcanzan complejidades óptimas en el peor de los casos para los montículos. Inicialmente se describieron como estructuras de datos imperativas. La cola de Brodal-Okasaki es una estructura de datos persistente que alcanza el mismo óptimo, excepto queno admite la operación de incremento de clave .

Notas

  1. ↑ Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert ; Munro, JI; Demaine, ED (1999), Resizable Arrays in Optimal Time and Space (Informe técnico CS-99-09) (PDF) , Departamento de Ciencias de la Computación, Universidad de Waterloo
  2. 1 2 3 Chris Okasaki (1995). "Listas de acceso aleatorio puramente funcionales". Actas de la Séptima Conferencia Internacional sobre Lenguajes de Programación Funcionales y Arquitectura de Computadoras : 86–95 . doi : 10.1145/224164.224187 .
  3. ↑ Mehlhorn, Kurt ; Sanders, Peter (2008), "4 Tablas hash y matrices asociativas", Algoritmos y estructuras de datos: La caja de herramientas básica (PDF) , Springer, págs. 81–98 , archivado (PDF) del original el 2 de agosto de 2014 
  4. ^ Cormen et al. 2022 , pág. 484.
  5. 1 2 3 4 Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L. (1990). Introducción a los algoritmos (1ª ed.). MIT Press y McGraw-Hill. ISBN  0-262-03141-8.
  6. 1 2 3 Sleator, Daniel Dominic ; Tarjan, Robert Endre (febrero de 1986). "Montículos autoajustables" . SIAM Journal on Computing . 15 (1): 52– 69. CiteSeerX 10.1.1.93.6678 . doi : 10.1137/0215004 . ISSN 0097-5397 .  
  7. 1 2 Tarjan, Robert (1983). "3.3. Montones izquierdistas". Estructuras de datos y algoritmos de red . págs. 38–42 . doi : 10.1137/1.9781611970265 . ISBN  978-0-89871-187-5.
  8. ↑ Hayward, Ryan; McDiarmid, Colin (1991). "Análisis del caso promedio de la construcción de montículos mediante inserción repetida" (PDF) . J. Algorithms . 12 : 126–153 . CiteSeerX 10.1.1.353.7888 . doi : 10.1016/0196-6774(91)90027-v . Archivado del original (PDF) el 5 de febrero de 2016. Recuperado el 28 de enero de 2016 . 
  9. ↑ "Montículo binomial | Brilliant Math & Science Wiki" . brilliant.org . Consultado el 30 de septiembre de 2019 .
  10. 1 2 Brodal, Gerth Stølting; Okasaki, Chris (noviembre de 1996), "Colas de prioridad puramente funcionales óptimas", Journal of Functional Programming , 6 (6): 839– 857, doi : 10.1017/s095679680000201x
  11. ↑ Okasaki, Chris (1998). "10.2. Abstracción estructural". Estructuras de datos puramente funcionales (1.ª ed.). págs. 158–162 . ISBN   9780521631242.
  12. ↑ Takaoka, Tadao (1999), Teoría de los montículos 2-3 (PDF) , pág. 12 
  13. ↑ Iacono, John (2000), "Improved upper bounds for pairing heaps", Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF) , Lecture Notes in Computer Science, vol. 1851, Springer-Verlag, pp. 63–77 , arXiv : 1110.4428 , CiteSeerX 10.1.1.748.7812 , doi : 10.1007/3-540-44985-X_5 , ISBN    3-540-67690-2
  14. ↑ Fredman, Michael Lawrence (julio de 1999). "Sobre la eficiencia de los montículos de emparejamiento y estructuras de datos relacionadas" (PDF) . Journal of the Association for Computing Machinery . 46 (4): 473– 501. doi : 10.1145/320211.320214 .
  15. ↑ Pettie, Seth (2005). Hacia un análisis final de los montículos de emparejamiento (PDF) . Actas de FOCS '05 del 46.º Simposio Anual IEEE sobre Fundamentos de la Informática. págs. 174–183 . CiteSeerX 10.1.1.549.471 . doi : 10.1109/SFCS.2005.75 . ISBN   0-7695-2468-0.
  16. ↑ Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (noviembre de 2011). "Montones de emparejamiento de rangos" (PDF) . SIAM J. Informática . 40 (6): 1463–1485.doi : 10.1137 / 100785351 .
  17. ↑ Fredman, Michael Lawrence ; Tarjan, Robert E. (julio de 1987). "Montículos de Fibonacci y sus usos en algoritmos mejorados de optimización de redes" (PDF) . Journal of the Association for Computing Machinery . 34 (3): 596– 615. CiteSeerX 10.1.1.309.8927 . doi : 10.1145/28869.28874 . 
  18. ↑ Brodal, Gerth Stølting ; Lagogiannis, George; Tarjan, Robert E. (2012). Montículos estrictos de Fibonacci (PDF) . Actas del 44.º simposio sobre Teoría de la Computación - STOC '12. págs. 1177–1184 . CiteSeerX 10.1.1.233.1740 . doi : 10.1145/2213977.2214082 . ISBN   978-1-4503-1245-5.
  19. ↑ Brodal, Gerth S. ( 1996), "Colas de prioridad eficientes en el peor de los casos" (PDF) , Actas del 7.º Simposio Anual ACM-SIAM sobre Algoritmos Discretos , págs. 52–58 
  20. ↑ Goodrich, Michael T .; Tamassia, Roberto (2004). "7.3.6. Construcción de montículos ascendentes". Estructuras de datos y algoritmos en Java (3.ª ed.). págs. 338–341 . ISBN   0-471-46983-1.

Referencias

  • Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (5 de abril de 2022). Introducción a los Algoritmos, cuarta edición . Prensa del MIT. ISBN 978-0-262-36750-9.