$ \ Phi_1= 1 $ o $ \ phi_1= 2 $ para el Dynamic $ \ Text {Table-Insert} $, donde $ \ phi_i $ es la función potencial después de $ i $ th Operación, según CLRS

Question

Los siguientes vienen de la sección Tablas dinámicas , Introducción a los algoritmos por Cormen. et. al.

---

En el siguiente pseudocode, asumimos que $ t $ es un objeto que representa la tabla. El campo $ Tabla [t] $ contiene un puntero al bloque de almacenamiento que representa la tabla. El campo $ num [t] $ contiene el número de elementos en la tabla y el campo $ size [t] $ es el número total de ranuras en la tabla. Inicialmente, la tabla está vacía: $ num [t]= tamaño [t]= 0 $ .

$ \ texto {table-insert (t, x)} $

$ 1 \ quad \ texto {si $ size [t]= 0 $} $

$ 2 \ quad \ quad \ text {luego asignar $ Tabla [t] $ con $ 1 $ slot} $

$ 3 \ quad \ quad \ quad [t] \ inmediato 1 $

$ 4 \ quad \ texto {if} num [t]= talla [t] $

$ 5 \ quad \ quad \ text {luego asignar $ nuevo {\ texto {-}} Tabla $ con $ 2 \ cdot size [t] $ slots} $

$ 6 \ quad \ quad \ quad \ texto {inserte todos los elementos en $ tabla [t] $ en $ nuevo {\ texto {-}} Table $} $

$ 7 \ quad \ quad \ quad \ text {Tabla gratis $ $ [t] $} $

$ 8 \ quad \ quad \ quad \ quad [t] \ inmediato nuevo {\ texto {-}} Tabla $

$ 9 \ quad \ quad \ quad \ quad [t] \ \ saltearro 2 \ cdot size [t] $

$ 10 \ quad \ texto {inserte $ x $ en $ tabla [t] $} $

$ 11 \ quad num [t] \ \ \ \ bitwarrow num [t] + 1 $

Para el análisis amortizado para la secuencia de una secuencia de $ n $ $ \ texto {table-insert} $ La función potencial que eligen es la siguiente,

$$ \ phi (t)= 2.num [t] -Size [t] $$

Para analizar el costo amortizado del $ i $ th $ \ texto {table-insert} $ Operación, le permitimos $ num_i $ denota el número de elementos almacenados en la tabla después del $ i $ Operación, $ size_i $ denota el tamaño total de la tabla después del $ i $ th Operación, y $ \ phi_i $ denota el potencial después del $ i $ th Operación.

Inicialmente, tenemos $ num_0= 0, size_0= 0 $ , y $ \ phi_0= 0 $ .

Si el $ i $ th la operación de inserción de tabla no provoca una expansión, entonces tenemos $ size_i= size_ {II} $ y $ num_i= num_ {i-1} +1 $ , el costo amortizado de la operación es $ \ widehat {c_i} $ es el costo amortizado y $ c_i $ es el costo total.

$$ \ widehat {c_i}= c_i + \ phi_i- \ phi_ {i-1}= 3 \ texto {(detalles no mostrados)} $$ < / p>

Si el $ i $ th Operación activa una expansión, entonces tenemos $ size_i= 2. size_ {I-1} $ y $ size_ {i-1}= num_ {i-1}= num_i -1 $ , así que otra vez, < / p>

$$ \ widehat {c_i}= c_i + \ phi_i- \ phi_ {i-1}= 3 \ texto {(detalles no mostrados)} $$ < / p>

---

Ahora, el problema es que no hacen cálculos para $ \ widehat {c_1} $ , la situación para la primera inserción de un Elemento en la tabla (línea 1,2,3,10,11 de código solo se ejecuta).

En esa situación, el costo $ c_1= 1 $ , $ \ phi_0= 0 $ y $ num_1= size_1= 1 \ implies \ phi_1= 2.1-1= 1 $

Vemos que $ \ phi_1= 1 \ etiqueta 1 $

Entonces, $$ \ widehat {c_1}= C_1 + \ PHI_1- \ PHI_0= 2 $$

Pero el texto dice que el costo amortizado es $ 3 $ , (Siento que deberían haber dicho que el costo amortizado es la más $ 3 $ , de lo que puedo entender)

Además en la parcela a continuación,

El texto representa gráficamente el $ \ phi_1= 2 $ que un tipo de contradictos

er "> $ (1) $ , pero según el gráfico si asumimos $ \ phi_1= 2 $ luego $ \ widehat {c_i}= 3, \ forall i $

No llego al lugar donde estoy haciendo lo confundido.

Answer 1

Ha atrapado una instancia del INFAMUSO OFERNO ERROR en ese libro de texto popular cuyo nombre no volveremos a mencionar.

Para repetir, es correcto que "el costo $ c_1= 1 $ , $ \ phi_0= 0 $ < / span> "," $ num_1= size_1= 1 $ $ \ implica $ $ \ phi_1= 2 \ cdot1-1= 1 $ " y " $ \ hat {c_1}= $ $ C_1 + \ PHI_1- \ PHI_0 $ $= 2 $ ". Es incorrecto afirmar que $ \ widehat c_i= 3 $ para todos $ i $ .

El primer $ \ texto {t} \ scriptsize {\ texto {capaz}} \ small \ text {-i} \ scriptsize \ texto {nsert} $ La operación es de hecho muy especial. No se considera como una expansión, un evento que se define como "en qué líneas 5-9 se ejecutan". Sin embargo, no mantiene $ size_i= size_ {i-1} $ , tampoco. Por lo que ni computación para $ \ widehat {c_i} $ en el libro de texto está en forma para $ \ widehat {c_1} $ .

Este error es confuso, dado que tendemos a confiar en un libro de texto completamente ejemplar donde se ha prestado tanta atención a los detalles y la corrección.

Por otro lado, ese error no es muy significativo, ya que, como señaló, todavía sostiene que "el costo amortizado es como máximo 3".

Por cierto, si se echa un vistazo más de cerca la figura al final de la pregunta, muestra el potencial al final del primer $ \ texto {t} \ scriptsize { \ texto {capaz}} \ small \ texto {-i} \ scriptsize \ texto {nsert} $ Operación, $ \ phi_1= 1 $ , el valor correcto.