¿Se consideran equivalentes el tiempo constante y el tiempo constante amortizado?

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, la mayoría de las posibilidades es que esté cubierto.

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

Sin embargo , tenga en cuenta que, de forma 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 del elemento eliminado. . 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 matrices y luego eliminar el último elemento, de modo que no se mueva ningún elemento. Pero luego, si haces eso, ya no tienes exactamente una cola.

Comentarios

• Maldita sea, buen punto sobre las eliminaciones; No ‘ lo consideré. Y dado que ‘ estamos eliminando elementos al azar, no ‘ t eso significa técnicamente que ‘ ¿Ya no es una cola en ese sentido de todos modos?
• Sí, significa que realmente no la está tratando como una cola. Pero no sé cómo planea encontrar los elementos para eliminar. Si su mecanismo para encontrarlos espera que estén presentes en la cola en el orden en que se agregaron, no tiene suerte.Si no le importa si el orden de los elementos se distorsiona, entonces está bien.
• La expectativa es que mi RandomQueue implemente el Queue interfaz, y para el método remove proporcionado para eliminar aleatoriamente en lugar de hacer estallar la cabeza, por lo que no debería haber ‘ No hay forma de confiar en un pedido específico. Creo que, dada la naturaleza aleatoria, el usuario no debería ‘ esperar que mantenga un orden específico. Cité la asignación en mi pregunta para aclarar. Gracias.
• Sí, entonces, parece que estará bien si solo se asegura de que la eliminación del elemento se realice de la manera que sugerí.
• Una última cosa si no ‘ t mente. ‘ lo he pensado más y no ‘ parece ‘ Es posible tener tanto » true » O (1) adiciones y » true » O (1) eliminación aleatoria; it ‘ será una compensación entre los 2. O tiene una estructura asignada individualmente (como una matriz) que proporciona eliminación pero no adición, o una estructura asignada por fragmentos como un Linked- Lista que proporciona adiciones pero no eliminaciones. ¿Es esto cierto? Nuevamente, gracias.

La pregunta parece pedir específicamente tiempo constante, y no una 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 tienes 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 el tiempo constante y el 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, búferes temporales, contenedores de trabajo), podría pagar efectivamente los costos solo una vez durante la ejecución.

En respuesta a aplicaciones críticas, estos tiempos pueden ser inaceptables. Si debe cumplir con una garantía de respuesta a corto plazo, no puede confiar en un algoritmo que ocasionalmente lo superará. He trabajado en proyectos de este tipo 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, aquí hay un pequeño problema. Para hacer cualquier contenedor de uso general ser tiempo constante para la inserción una de dos cosas debe ser válida:

• 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 .

Comentarios

• » servidor de hígado » parece una frase extraña para usar aquí. ¿Te refieres a » servidor en vivo » quizás?

Depende – de si está optimizando para rendimiento o latencia:

• Latencia- Los sistemas sensibles necesitan un rendimiento constante. Para tal escenario, tenemos que enfatizar el comportamiento del sistema en el peor de los casos. Por ejemplo, los sistemas blandos en tiempo real, como s juegos que quieren lograr una velocidad de fotogramas constante, o servidores web que tienen que enviar una respuesta dentro de un período de tiempo limitado: desperdiciar ciclos de CPU es mejor que llegar tarde.
• Los sistemas de rendimiento optimizado no se preocupan por paradas ocasionales, siempre que se pueda procesar la máxima cantidad de datos a largo plazo. En este caso, nos interesa principalmente el rendimiento amortizado. Este es generalmente el caso de procesamiento 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. P.ej. un procesador de texto moderno tendría un subproceso de IU sensible a la latencia, pero subprocesos con rendimiento optimizado para otras tareas, como la revisión ortográfica o las exportaciones de PDF.

Además, la complejidad algorítmica a menudo no importa tanto como podríamos Piense: cuando un problema está limitado a un número determinado, las características de rendimiento reales y medidas son más importantes que el comportamiento «para n » muy grandes.

Comentarios

• Desafortunadamente, tengo muy pocos antecedentes.La pregunta termina con: » Las operaciones add (x) y remove () en RandomQueue deben ejecutarse en tiempo constante por operación «.
• @Carcigenicate a menos que sepa con certeza que el sistema es sensible a la latencia, usar la complejidad amortizada para seleccionar una estructura de datos debería ser absolutamente suficiente.
• Tengo la impresión de que esto podría ser un ejercicio de programación o una prueba. Y ciertamente no es fácil. Es absolutamente cierto que rara vez importa.

Si se le solicita un «tiempo constante amortizado» algoritmo, su algoritmo puede a veces 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 lleva un tiempo considerable. Pero si agrega un millón de objetos, puede tener 999,980 operaciones rápidas y 20 lentas, siendo el tiempo promedio rápido.

Si se le solicita un algoritmo de «tiempo constante», su algoritmo debe siempre 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. El «tiempo constante» no suele ser necesario, pero definitivamente no es lo mismo que el «tiempo constante amortizado».