Curso 2024/2025
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(n2). 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.