Algoritmos y Estructuras de Datos (VJ1215)

El coste temporal en el peor caso de la operación apilar es O(n), siendo n la talla de la pila (la cantidad de datos que contiene en ese momento). El peor caso se da cuando el vector está lleno y se redimensiona duplicando su tamaño y copiando en el nuevo vector los elementos que contenía el anterior.

Teniendo en cuenta el coste en el peor caso de apilar, podría parecer que el coste en el peor caso de ese bucle es 0(n²). Sin embargo, ese no es un análisis preciso, es extremadamente pesimista, porque no sucede que todas las llamadas dentro del bucle cuesten O(n): la mayoría cuestan O(1) porque no necesitan redimensionar el vector.

Un análisis más preciso consiste en observar que el coste total del bucle es la suma de:

• O(1 + 1 + 1 + 1 + 1 + ... + 1) = O(n), porque cuesta O(1) insertar el nuevo dato en el vector en cada una de las n llamadas.

• O(1 + 2 + 4 + 8 + 16 + ... + n) = O(n), que es el coste de copiar los elementos del vector anterior todas las veces que se redimensiona el vector duplicando su tamaño.

Eso nos da un coste total, en el peor caso, de O(n + n) = O(n).

El coste amortizado de cada llamada a apilar es O(1): es el resultado de repartir por igual entre cada una de las operaciones apilar el coste total en el peor caso de realizar n operaciones apilar consecutivas.