Método contable (informática)

A menudo es necesario crear una tabla antes de saber cuánto espacio se necesita. Una estrategia posible es duplicar el tamaño de la tabla cuando esté llena. Aquí utilizaremos el método contable para demostrar que el costo amortizado de una operación de inserción en dicha tabla es O (1).

Antes de analizar el procedimiento en detalle, necesitamos algunas definiciones. Sea T una tabla, E un elemento a insertar, num(T) el número de elementos en T y size(T) el tamaño asignado a T. Suponemos la existencia de las operaciones create_table(n), que crea una tabla vacía de tamaño n , que por ahora se supone gratuita, y elementary_insert(T,E), que inserta el elemento E en una tabla T que ya tiene espacio asignado, con un coste de 1.

El siguiente pseudocódigo ilustra el procedimiento de inserción en la tabla:

función table_insert(T, E) si num(T) = size(T) U := crear_tabla(2 × tamaño(T)) para cada F en T inserción_elemental(U, F) T := U inserción_elemental(T, E)

Sin un análisis amortizado, la mejor cota que podemos mostrar para n operaciones de inserción es O(n) — esto se debe al bucle en la línea 4 que realiza num(T) inserciones elementales.

Para el análisis mediante el método contable, asignamos un pago de 3 a cada inserción en la tabla. Si bien el motivo de esto no está claro ahora, se aclarará durante el transcurso del análisis.

Supongamos que inicialmente la tabla está vacía con tamaño(T) = m. Por lo tanto, las primeras m inserciones no requieren reasignación y solo tienen un costo de 1 (para la inserción elemental). En consecuencia, cuando num(T) = m, el pool tiene (3 - 1) × m = 2m.

La inserción del elemento m + 1 requiere la reasignación de la tabla. La creación de la nueva tabla en la línea 3 es gratuita (por ahora). El bucle en la línea 4 requiere m inserciones elementales, con un coste de m. Incluyendo la inserción en la última línea, el coste total de esta operación es m + 1. Por lo tanto, después de esta operación, el pool tiene 2m + 3 - (m + 1) = m + 2.

A continuación, añadimos otros m - 1 elementos a la tabla. En este punto, el pool tiene m + 2 + 2 × (m - 1) = 3m. Se observa que insertar un elemento adicional (es decir, el elemento 2m + 1) tiene un coste de 2m + 1 y un pago de 3. Tras esta operación, el pool tiene 3m + 3 - (2m + 1) = m + 2. Nótese que esta es la misma cantidad que después de insertar el elemento m + 1. De hecho, podemos demostrar que esto ocurrirá con cualquier número de reasignaciones.

Ahora se entiende por qué el pago por una inserción es 3. 1 paga por la primera inserción del elemento, 1 paga por mover el elemento la próxima vez que se expanda la tabla, y 1 paga por mover un elemento anterior la próxima vez que se expanda la tabla. Intuitivamente, esto explica por qué la contribución de un elemento nunca se agota, independientemente de cuántas veces se expanda la tabla: dado que la tabla siempre se duplica, la mitad más reciente siempre cubre el costo de mover la mitad más antigua.

Inicialmente asumimos que crear una tabla era gratis. En realidad, crear una tabla de tamaño n puede ser tan costoso como O(n). Digamos que el costo de crear una tabla de tamaño n es n. ¿Presenta este nuevo costo alguna dificultad? En realidad no; resulta que usamos el mismo método para demostrar los límites amortizados de O(1). Lo único que tenemos que hacer es cambiar el pago.

Cuando se crea una tabla nueva, existe una tabla antigua con m entradas. La nueva tabla tendrá un tamaño de 2m. Siempre que las entradas que ya contiene la tabla hayan aportado lo suficiente al fondo común para cubrir el coste de la creación de la nueva tabla, todo irá bien.

No podemos esperar el primero${\displaystyle {\frac {m}{2}}}$entradas para ayudar a pagar la nueva mesa. Esas entradas ya pagaron la mesa actual. Entonces debemos confiar en la última${\displaystyle {\frac {m}{2}}}$entradas para pagar el costo${\displaystyle 2m}$Esto significa que debemos añadir${\displaystyle {\frac {2m}{m/2}}=4}$al pago por cada entrada, para un pago total de 3 + 4 = 7.