¿El tiempo constante y el tiempo constante amortizado se consideran efectivamente equivalentes?

Necesito escribir un RandomQueue que permita anexos y eliminación aleatoria en tiempo constante (O (1)).

Mi primer pensamiento fue respaldarlo con algún tipo de Array (elegí una ArrayList), ya que las matrices tienen acceso constante a través de un índice.

Sin embargo, al revisar la documentación, me di cuenta de que las adiciones de ArrayLists se consideran tiempo constante amortizado, ya que una adición puede requerir una reasignación de la matriz subyacente, que es O (n).

¿Son el tiempo constante amortizado y el tiempo constante efectivamente iguales, o necesito mirar alguna estructura que no requiera una reasignación completa en cada adición?

Estoy preguntando esto porque, aparte de las estructuras basadas en matrices (que, hasta donde yo sé, siempre tendrán adiciones de tiempo constante amortizado), no puedo pensar en nada que cumpla con los requisitos:

• Cualquier cosa basada en un árbol tendrá, en el mejor de los casos, O (log n)
• Una lista vinculada podría tener adiciones de O (1) (si se mantiene una referencia a la cola), pero una eliminación aleatoria debería ser, en el mejor de los casos, O (n).

Aquí está la pregunta completa; en caso de que haya visto algunos detalles importantes:

Diseñar e implementar un RandomQueue. Esta es una implementación de la interfaz de cola en la que la operación remove () elimina un elemento que se elige de manera uniforme al azar entre todos los elementos actualmente en la cola. (Piense en un RandomQueue como una bolsa en la que podemos agregar elementos o alcanzar y eliminar ciegamente algún elemento aleatorio). Las operaciones add (x) y remove () en un RandomQueue deben ejecutarse en tiempo constante por operación.

El tiempo constante amortizado casi siempre se puede considerar equivalente al tiempo constante, y sin conocer los detalles de su aplicación y el tipo de uso que planea hacer para esta cola, lo más probable es que esté cubierto.

Una lista de matriz tiene el concepto de capacidad , que es básicamente igual al mayor tamaño / longitud / recuento de elementos que se le haya requerido hasta ahora. Entonces, lo que sucederá es que al principio la lista de matrices seguirá reasignándose para aumentar su capacidad a medida que continúe agregando elementos, pero en algún momento el número promedio de elementos agregados por unidad de tiempo inevitablemente coincidirá con el número promedio de elementos eliminado por unidad de tiempo (de lo contrario, se quedaría sin memoria de todos modos), momento en el que la matriz dejará de reasignarse y todos los apéndices se cumplirán en el tiempo constante de O (1).

Sin embargo, tenga en cuenta que, de manera predeterminada, la eliminación aleatoria de una lista de matriz no es O (1), es O (N), porque las listas de matriz mueven todos los elementos después del elemento eliminado una posición hacia abajo para tomar el lugar de los elementos eliminados. articulo. Para lograr O (1), tendrá que anular el comportamiento predeterminado para reemplazar el elemento eliminado con una copia del último elemento de la lista de la matriz, y luego eliminar el último elemento, para que no se mueva ningún elemento. Pero entonces, si haces eso, ya no tienes exactamente una cola.

La pregunta parece pedir específicamente un tiempo constante, y no un tiempo constante amortizado . Entonces, con respecto a la pregunta citada, no, no son efectivamente lo mismo *. ¿Sin embargo están en aplicaciones del mundo real?

El problema típico con la constante amortizada es que ocasionalmente tiene que pagar la deuda acumulada. Entonces, aunque las inserciones son generalmente constantes, a veces tiene que sufrir la sobrecarga de reinsertar todo nuevamente cuando se asigna un nuevo bloque.

Donde la diferencia entre tiempo constante y tiempo constante amortizado es relevante para una aplicación depende de si esta velocidad muy lenta ocasional es aceptable. Para una gran cantidad de dominios, esto generalmente está bien. Especialmente si el contenedor tiene un tamaño máximo efectivo (como cachés, amortiguadores temporales, contenedores de trabajo), puede pagar sus costos de manera efectiva solo una vez durante la ejecución.

En respuesta, las aplicaciones críticas estos tiempos pueden ser inaceptables. Si debe cumplir con una garantía de respuesta de corto plazo, no puede confiar en un algoritmo que ocasionalmente excederá eso. He trabajado en tales proyectos antes, pero son extremadamente raros.

También depende de qué tan alto sea realmente este costo. Los vectores tienden a funcionar bien ya que su costo de reasignación es relativamente bajo. Sin embargo, si va al mapa hash, la reasignación puede ser mucho mayor. Aunque de nuevo, para la mayoría de las aplicaciones probablemente esté bien, especialmente los servidores de mayor duración con un límite superior en los elementos del contenedor.

* Sin embargo, hay un pequeño problema aquí. Para que cualquier contenedor de uso general sea un tiempo constante para la inserción, debe contener una de dos cosas:

• El contenedor debe tener un tamaño máximo fijo; o
• puede asumir que la asignación de memoria de elementos individuales es tiempo constante.

Depende de si está optimizando el rendimiento o la latencia:

• Los sistemas sensibles a la latencia necesitan un rendimiento constante. Para tal escenario, tenemos que enfatizar el peor comportamiento del sistema. Algunos ejemplos son los sistemas blandos en tiempo real, como los juegos que desean alcanzar una velocidad de fotogramas constante, o los servidores web que tienen que enviar una respuesta dentro de un período de tiempo limitado: perder los ciclos de la CPU es mejor que llegar tarde.
• Los sistemas optimizados de rendimiento no se preocupan por las paradas ocasionales, siempre que la cantidad máxima de datos se pueda procesar a largo plazo. Aquí, estamos principalmente interesados ​​en el rendimiento amortizado. Este suele ser el caso de la suma de números u otros trabajos de procesamiento por lotes.

Tenga en cuenta que un sistema puede tener diferentes componentes que deben clasificarse de manera diferente. Por ejemplo, un procesador de texto moderno tendría un subproceso de interfaz de usuario sensible a la latencia, pero subprocesos optimizados para otras tareas, como la corrección ortográfica o las exportaciones de PDF.

Además, la complejidad algorítmica a menudo no importa tanto como podríamos pensar: cuando un problema se limita a un cierto número, las características de rendimiento reales y medidas son más importantes que el comportamiento "para n muy grande ".

Si se le solicita un algoritmo de "tiempo constante amortizado", su algoritmo a veces puede llevar mucho tiempo. Por ejemplo, si usa std :: vector en C ++, dicho vector puede haber asignado espacio para 10 objetos, y cuando asigna el undécimo objeto, se asigna espacio para 20 objetos, se copian 10 objetos y se agrega el undécimo, que Toma un tiempo considerable. Pero si agrega un millón de objetos, puede tener 999,980 operaciones rápidas y 20 operaciones lentas, con un tiempo promedio rápido.

Si se le solicita un algoritmo de "tiempo constante", su algoritmo siempre debe ser rápido, para cada operación. Eso sería importante para los sistemas en tiempo real donde podría necesitar una garantía de que cada operación sea siempre rápida. "Tiempo constante" a menudo no es necesario, pero definitivamente no es lo mismo que "tiempo constante amortizado".