c# - restricciones - ¿Cómo puede la Propiedad List<T>.Item ser O(1)? ¿Error de tipografía?
no se pudo incrustar la fuente en el documento pdf debido a restricciones de licencia (7)
Estoy implementando una cola de prioridad y quiero iterar a través de la lista para insertarla en el lugar correcto. En la documentación indica que C # List<T>.Item Property es O (1): List<T>.Item Property
p.ej
int retrivedValue = myIntList[5];
¿Cómo es posible porque add también es O (1)? Es como comer la galleta y aún tenerla. Las listas normales en mi cabeza tienen O (n) para acceder a un elemento.
El tipo de Lista estándar está respaldado por una matriz interna con el rendimiento de acceso O (1).
List no usa una implementación de lista enlazada .
La List<T> está respaldada por una matriz.
La operación Add es O (1) amortizada en todas las adiciones , lo que significa que la mayoría de las operaciones son O (1), pero algunas son O (N). Cada vez que el conjunto de respaldo se llena, se copia a una nueva matriz de doble tamaño.
Como ejemplo de cómo funciona, supongamos que la matriz de respaldo comienza con 4 elementos. Las primeras 4 adiciones son O (1), pero la 5ª tendrá que copiar los 4 elementos existentes y agregar la 5ª, por lo que es O (5). Agregar los elementos 6, 7 y 8 es O (1), mientras que agregar el elemento 9 será O (9). Entonces los elementos 10-16 también serán O (1).
Cuando hayas agregado 16 elementos a la matriz, has realizado O (28) operaciones, por lo que la adición de N elementos toma casi O (2N) operaciones. Por lo tanto, agregar un solo elemento es O (2) = O (1) en promedio.
La lista interna usa una matriz, por lo que la indexación es una operación directa. Además, agregar al final es rápido (a menos que se requiera un realoc). Sin embargo, Insertar y Eliminar son O (n), porque todos los elementos de la matriz deben moverse. En la práctica, esto no es tan malo también, porque el movimiento se implementa como un solo movimiento de bloque de la parte derecha de la matriz.
Solo tiene O(n) si tiene que recorrer la lista para recuperar el artículo.
Para este ejemplo, está accediendo a una matriz interna por índice, por lo que no tiene que iterar.
Es posible que desee ver esto para comprender y, sin embargo, utilizar la estructura de datos más adecuada.
A continuación se muestra la tabla de resumen:
List<T> es una lista en representación, como dice la documentación, representa una lista de objetos tipeados a los que se puede acceder por índice . Se puede acceder directamente a sus elementos por índice y no requiere un recorrido elemento por elemento, por lo tanto, es hora de que la complejidad para acceder a un elemento sea O (1). Se implementa internamente como una matriz dinámica, del tipo que duplica su tamaño cuando se llena (¡gracias a los comentarios!).
Puede confundirlo con LinkedList<T> , que se implementa como una lista vinculada ...
A pesar de la atractiva complejidad de Búsqueda de listas basada en el índice de elementos, me pregunto si sus necesidades podrían mejorarse con SkipList como se describe en Un examen exhaustivo de estructuras de datos con C # 2.0 aludido aquí , ya que la prioridad de ordenamiento no es única.
La extensión dinámica de una matriz para n inserciones (n ilimitadas) es, de hecho, O (n)
Si un respaldo de matriz de una lista se duplica en tamaño cada vez y se permite que n crezca sin límite, el número de veces que se volverá a asignar la matriz será O (logn) y en cada punto será de tamaño 2 ^ k; k = 1,2,3 ...
List<T>.Item versus List<T>.Contains
El acceso a los elementos en una lista es O (1) si se conoce el índice, pero para mantener el orden correcto según la prioridad, necesitaría usar algún mecanismo de ordenamiento externo o usar .Contains , pero ese segundo método no es O (1)
Los saltadores tienen complejidad de búsqueda O (logn); permite una Enqueue O (logn) de PriorityQueue y O (1) dequeue
La idea es que una lista de exclusión es una lista vinculada con punteros "de avance rápido" insertados al azar para superar la complejidad de la búsqueda O (n) de la lista de enlaces. Cada nodo tiene una altura K y K los siguientes punteros. Sin entrar en detalles, las alturas se distribuyen y la función next () selecciona el puntero apropiado de tal forma que se realice la búsqueda O (logn). Sin embargo, el nodo para eliminar de la cola siempre estará en un extremo de la lista vinculada.
Comportamiento en línea
La memoria es finita y, en términos prácticos, una cola de prioridad no va a crecer para siempre. Se podría argumentar que la cola crece hasta cierto tamaño y luego nunca se reasigna. Pero entonces, ¿se encoge? Si la lista se fragmenta, una operación de reducción suena aún más costosa que la operación de crecimiento. Si se admite el encogimiento, el costo se pagará cada vez que la Lista crezca demasiado pequeña y luego se pagará el costo de crecimiento cuando la Lista crezca demasiado. Si no es compatible, la memoria asociada con el tamaño de cola más grande permanecerá asignada. Al tratarse de una cola de prioridad, de hecho parece posible que una cola crezca a medida que se ingresa trabajo, y luego se reduce (lógicamente) a 0. Puede haber circunstancias excepcionales en las que crecerá mucho si el lado del consumidor se retrasa.