Costo amortizado de insertar / eliminar en min-heap
Recientemente me encontré con una pregunta de la entrevista. no se da información adicional en cuestión (tal vez se deba usar la implementación predeterminada ...)
n secuencias arbitrarias de operaciones de inserción y eliminación en un montón mínimo vacío ( se conoce la ubicación del elemento de eliminación ) tiene un costo amortizado de:
A) inserte O (1), quite O (log n)
B) inserte O (log n), quite O (1)
La opción ( B ) es correcta.
Me sorprende ver la hoja de respuestas. sé que esto es complicado, tal vez un montón vacío, tal vez conociendo la ubicación de los elementos para eliminar, ... no sé por qué (A) es falso? ¿Por qué (B) es cierto?
Respuestas
Al asignar costos amortizados a operaciones en una estructura de datos, debe asegurarse de que, para cualquier secuencia de operaciones realizadas, la suma de los costos amortizados sea siempre al menos tan grande como la suma de los costos reales de esas operaciones.
Entonces, tomemos la Opción 1, que asigna un costo amortizado de O (1) a las inserciones y un costo amortizado de O (log n) a las eliminaciones. La pregunta que tenemos que hacernos es la siguiente: ¿es cierto que para cualquier secuencia de operaciones en un montón binario vacío, el costo real de esas operaciones está limitado por el costo amortizado de esas operaciones? Y en este caso, la respuesta es no. Imagina que haces una secuencia puramente de n inserciones en el montón. El costo real de realizar estas operaciones puede ser Θ (n log n) si cada elemento tiene que burbujear hasta la parte superior del montón. Sin embargo, el costo amortizado de esas operaciones, con este esquema contable, sería O (n), ya que hicimos n operaciones y pretendíamos que cada una costaba O (1) tiempo. Por tanto, este esquema contable amortizado no funciona, ya que nos permitirá subestimar el trabajo que estamos haciendo.
Por otro lado, veamos la Opción 2, donde asignamos O (log n) como nuestro costo de inserción amortizado y O (1) como nuestro costo de eliminación amortizado. Ahora bien, ¿podemos encontrar una secuencia de n operaciones donde el costo real de esas operaciones exceda los costos amortizados? En este caso, la respuesta es no. Aquí hay una forma de ver esto. Hemos establecido el costo amortizado de una inserción en O (log n), que coincide con su costo real, por lo que la única forma en que podríamos terminar subestimando el total es con nuestro costo amortizado de una eliminación (O (1) ), que es menor que el costo real de una eliminación. Sin embargo, eso no es un problema aquí. Para que podamos hacer una operación de eliminación, tenemos que haber insertado previamente el elemento que estamos eliminando. El costo real combinado de la inserción y la eliminación es O (log n) + O (log n) = O (log n), y el costo amortizado combinado de la inserción y la eliminación es O (log n) + O (1 ) = O (log n). Entonces, en ese sentido, pretender que las eliminaciones son más rápidas no cambia nuestro costo general.
Una forma agradable e intuitiva de ver por qué funciona el segundo enfoque, pero el primero no es pensar en qué se trata el análisis amortizado. La intuición detrás de la amortización es cobrar un poco más las operaciones anteriores para que las operaciones futuras parezcan llevar menos tiempo. En el caso del segundo esquema de contabilidad, eso es exactamente lo que estamos haciendo: estamos trasladando el costo de la eliminación de un elemento del montón binario al costo de insertar ese elemento en el montón en primer lugar. De esa manera, dado que solo estamos desplazando el trabajo hacia atrás, la suma de los costos amortizados no puede ser menor que la suma de los costos reales. Por otro lado, en el primer caso, estamos adelantando el trabajo en el tiempo haciendo que las eliminaciones paguen por las inserciones. Pero eso es un problema, porque si hacemos un montón de inserciones y luego nunca hacemos las eliminaciones correspondientes, habremos trasladado el trabajo a operaciones que no existen.
Debido a que el montón está inicialmente vacío, no puede tener más eliminaciones que inserciones.
Un costo amortizado de O (1) por eliminación y O (log N) por inserción es exactamente lo mismo que un costo amortizado de O (log N) tanto para inserciones como para eliminaciones, porque puede simplemente contar el costo de eliminación cuando hace lo inserto correspondiente.
No funciona al revés. Dado que puede tener más inserciones que eliminaciones, es posible que no haya suficientes eliminaciones para pagar el costo de cada inserción.