data structures - las - ¿Cuál es la complejidad del tiempo de indexación, inserción y eliminación de estructuras de datos comunes?

tipos de datos abstractos en java

Question

No hay un resumen disponible de la notación O grande para operaciones en las estructuras de datos más comunes, incluidas matrices, listas enlazadas, tablas hash, etc.

Answer 1

Árboles rojo-negro:

• Insertar - O (log n)
• Recuperar - O (log n)
• Eliminar - O (log n)

Answer 2

Amortizado Big-O para hashtables:

• Insertar - O (1)
• Recuperar - O (1)
• Eliminar - O (1)

Tenga en cuenta que hay un factor constante para el algoritmo hashing, y la amortización significa que el rendimiento real medido puede variar drásticamente.

Answer 3

La información sobre este tema ya está disponible en Wikipedia en: Estructura de datos de búsqueda

+----------------------+----------+------------+----------+--------------+
|                      |  Insert  |   Delete   |  Search  | Space Usage  |
+----------------------+----------+------------+----------+--------------+
| Unsorted array       | O(1)     | O(1)       | O(n)     | O(n)         |
| Value-indexed array  | O(1)     | O(1)       | O(1)     | O(n)         |
| Sorted array         | O(n)     | O(n)       | O(log n) | O(n)         |
| Unsorted linked list | O(1)*    | O(1)*      | O(n)     | O(n)         |
| Sorted linked list   | O(n)*    | O(1)*      | O(n)     | O(n)         |
| Balanced binary tree | O(log n) | O(log n)   | O(log n) | O(n)         |
| Heap                 | O(log n) | O(log n)** | O(n)     | O(n)         |
| Hash table           | O(1)     | O(1)       | O(1)     | O(n)         |
+----------------------+----------+------------+----------+--------------+

 * The cost to add or delete an element into a known location in the list (i.e. if you have an iterator to the location) is O(1). If you don''t know the location, then you need to traverse the list to the location of deletion/insertion, which takes O(n) time. 
** The deletion cost is O(log n) for the minimum or maximum, O(n) for an arbitrary element.

Answer 4

Supongo que comenzaré con la complejidad del tiempo de una lista vinculada:

Indexación ----> O (n)
Inserción / eliminación al final ----> O (1) o O (n)
Insertar / Borrar en el medio ---> O (1) con el iterador O (n) sin salida

La complejidad del tiempo para la inserción al final depende si tiene la ubicación del último nodo, si lo hace, sería O (1) de otra manera tendrá que buscar a través de la lista vinculada y la complejidad del tiempo saltará a O (norte).

Answer 5

Tenga en cuenta que, a menos que esté escribiendo su propia estructura de datos (por ejemplo, lista vinculada en C), puede depender drásticamente de la implementación de las estructuras de datos en su idioma / marco de referencia. Como ejemplo, eche un vistazo a los puntos de referencia de CFArray de Apple en Ridiculous Fish . En este caso, el tipo de datos, un CFArray del marco de CoreFoundation de Apple, en realidad cambia las estructuras de datos dependiendo de cuántos objetos hay realmente en la matriz, cambiando de tiempo lineal a tiempo constante en alrededor de 30,000 objetos.

Esta es una de las cosas más bellas de la programación orientada a objetos: no necesita saber cómo funciona, solo que funciona, y el ''cómo funciona'' puede cambiar según los requisitos.