data structures - notacion - Arreglos de notación O grande vs. inserciones de listas vinculadas

dominio asintotico

Question

Arreglos de notación O grande frente a inserciones de listas vinculadas:

Según la literatura académica para matrices, es constante O (1) y para Listas enlazadas es lineal O (n).

Una matriz solo toma una multiplicación y suma.

Una lista enlazada que no se presenta en la memoria contigua requiere un recorrido transversal.

Esta pregunta es: ¿O (1) y O (n) describen con precisión los costos de indexación / búsqueda para matrices y listas vinculadas respectivamente?

Answer 1

¿A qué literatura estás haciendo referencia? El tamaño de una matriz se determina cuando se crea la matriz, y nunca cambia después. La inserción realmente solo puede tener lugar en las ranuras libres al final de la matriz. Cualquier otro tipo de inserción puede requerir un cambio de tamaño y esto ciertamente no es O(1) . El tamaño de una lista vinculada depende de la implementación, pero siempre debe ser al menos lo suficientemente grande como para almacenar todos sus elementos. Los elementos se pueden insertar en cualquier lugar de la lista, y para encontrar el índice adecuado es necesario recorrerlos.

Answer 2

Hace mucho tiempo, en un sistema que tenía más RAM que espacio en disco, implementé una lista enlazada indexada que se indexó tal como se ingresó manualmente o cuando se cargó desde el disco. Todos y cada uno de los registros se adjuntaron al siguiente índice en la memoria y el archivo de disco abrió el registro adjunto al final cerrado.

El programa cobró las ventas en subasta en una computadora Modelo I Radio Shack y las escrituras en el disco fueron solo un seguro contra cortes de energía y un registro archivado para cumplir con las restricciones de tiempo que los datos debían ser recuperados desde la RAM e impresos en orden inverso. el comprador podría preguntar si el primer artículo que apareció fue el último que compró. Cada comprador y Vendedor se vincularon al último artículo de ellos que se vendió y ese artículo se vinculó al artículo anterior. Fue solo una lista de enlaces de un solo enlace que se recorrió de abajo hacia arriba.

Las correcciones se realizaron con reversión de entradas. Utilicé el mismo método para varias cosas y nunca encontré un sistema más rápido si el método funcionaría para el trabajo en cuestión y el índice se guardó en el disco y no fue necesario reconstruirlo, ya que el archivo se volvió a cargar en la memoria como debería. un apagón

Más tarde escribí un programa para editar más convencionalmente. También podría reorganizar los datos para agruparlos.

Answer 3

La inserción para matrices que imagino es más lenta. Claro, debe iterar una lista vinculada, pero debe asignar, guardar y desasignar la memoria para insertarla en una matriz.

Answer 4

Suponiendo que está hablando de una inserción donde ya conoce el punto de inserción, es decir, esto no tiene en cuenta el recorrido de la lista para encontrar la posición correcta:

Las inserciones en una matriz dependen de dónde se está insertando, ya que tendrá que cambiar los valores existentes. El peor de los casos (la inserción en la matriz [0]) es O (x).

La inserción en una lista es O (1) porque solo necesita modificar los punteros siguientes / anteriores de los elementos adyacentes.

Answer 5

O(1) describe con precisión la inserción al final de la matriz. Sin embargo, si está insertando en el medio de una matriz, tiene que cambiar todos los elementos después de ese elemento, por lo que la complejidad para la inserción en ese caso es O(n) para las matrices. La finalización de anexos también descuenta el caso en el que tendría que cambiar el tamaño de una matriz si está llena.

Para la lista enlazada, tiene que atravesar la lista para hacer inserciones intermedias, por lo que es O(n) . Aunque no tienes que cambiar los elementos hacia abajo.

Hay un buen gráfico en wikipedia con esto: http://en.wikipedia.org/wiki/Linked_list#Linked_lists_vs._dynamic_arrays

 Linked list Array Dynamic array Balanced tree
Indexing Θ(n) Θ(1) Θ(1) Θ(log n)
Insert/delete at beginning Θ(1) N/A Θ(n) Θ(log n)
Insert/delete at end Θ(1) N/A Θ(1) amortized Θ(log n)
Insert/delete in middle search time
+ Θ(1) N/A Θ(n) Θ(log n)
Wasted space (average) Θ(n) 0 Θ(n)[2] Θ(n)

Answer 6

tldr Una matriz sin clasificar es análoga a un conjunto. Al igual que un conjunto, los elementos se pueden agregar y eliminar, iterar y leer. Pero, al igual que con un conjunto, no tiene sentido hablar de insertar un elemento en una posición específica, ya que hacerlo sería un intento de imponer un orden de clasificación en lo que es, por definición, sin clasificar.

Según la literatura académica para matrices, es constante O (1) y para Listas enlazadas es lineal O (n).

Vale la pena comprender por qué la literatura académica cita el inserto de matriz como O (1) para una matriz. Hay varios conceptos para entender:

• Una matriz se define como sin clasificar (a menos que se indique explícitamente lo contrario).

• La longitud de una matriz, definida como el número de elementos que contiene la matriz, se puede aumentar o disminuir arbitrariamente en el tiempo O (1) y no hay límite en el tamaño máximo de una matriz.

  (En una computadora real, este no es el caso, debido a diversos factores como el tamaño de la memoria, la memoria virtual, el espacio de intercambio, etc. Pero a los efectos del análisis asintótico de algoritmos , estos factores no son importantes. de los cambios del algoritmo a medida que el tamaño de la entrada aumenta hacia el infinito, no cómo se realiza en una computadora en particular con un tamaño de memoria y sistema operativo en particular.)

• Insertar y delete son O (1) porque la matriz es una estructura de datos sin clasificar.

• Insertar no es asignación

Considere lo que realmente significa agregar un elemento a una estructura de datos sin clasificar. Dado que no hay un orden de clasificación definido, cualquier orden que ocurra realmente es arbitrario y no importa. Si piensas en términos de una API orientada a objetos, la firma del método sería algo así como:

Array.insert(Element e)

Tenga en cuenta que esto es lo mismo que los métodos de inserción para otras estructuras de datos, como una lista vinculada o una matriz ordenada:

LinkedList.insert(Element e)
SortedArray.insert(Element e)

En todos estos casos, la persona que llama al método de inserción no especifica dónde se almacena el valor que se inserta, es un detalle interno de la estructura de datos. Además, no tiene sentido que la persona que llama intente insertar un elemento en una ubicación específica de la estructura de datos, ya sea para una estructura de datos ordenada o no clasificada. Para una lista enlazada (sin clasificar), la lista es por definición sin clasificar y, por lo tanto, el orden de clasificación es irrelevante. Para una matriz ordenada, la operación de inserción, por definición, insertará un elemento en un punto específico de la matriz.

Por lo tanto, no tiene sentido definir una operación de inserción de matriz como:

Array.insert(Element e, Index p)

Con una definición de este tipo, el autor de la llamada anularía una propiedad interna de la estructura de datos e impondría una restricción de orden en una matriz no clasificada, una restricción que no existe en la definición de la matriz, porque una matriz no está clasificada.

¿Por qué ocurre este error con los arreglos y no con otras estructuras de datos? Probablemente porque los programadores están acostumbrados a tratar con matrices utilizando el operador de asignación:

array[0] = 10
array[1] = 20

El operador de asignación da a los valores de una matriz un orden explícito. Lo importante a tener en cuenta aquí es que la asignación no es lo mismo que insertar :

• insertar : almacene el valor dado en la estructura de datos sin modificar los elementos existentes.
• inserte en sin clasificar : almacene el valor dado en la estructura de datos sin modificar los elementos existentes y el orden de recuperación no es importante.
• inserte en ordenado : almacene el valor dado en la estructura de datos sin modificar los elementos existentes y el orden de recuperación es importante.
• asigne un [x] = v : sobrescriba los datos existentes en la ubicación x con el valor dado v .

Una matriz no clasificada no tiene orden de clasificación y, por lo tanto, la inserción no necesita permitir la anulación de la posición. Insertar no es lo mismo que la asignación . La inserción de matriz se define simplemente como:

Array.insert(v):
array.length = array.length + 1
// in standard algorithmic notation, arrays are defined from 1..n not 0..n-1
array[array.length] = v

Que es O (1).