Se encola n = 30 veces y después se desencolan
los 30, sobre cuatro listas de abajo distintas. Se cuentan los elementos
tocados: los que se corren en el arreglo y los nodos que se visitan en la
enlazada.
1. Las cuatro combinaciones
Con n = 30, ¿cuántos elementos toca cada una? En el orden
de la tabla: arreglo entrando por el final, arreglo entrando por el frente,
enlazada simple y enlazada con puntero al último.
tocados:
2. Cómo crecen
n
arreglo, entra al final
arreglo, entra al frente
enlazada simple
enlazada con ultimo
Al doblar n, las tres primeras columnas se
multiplican por cuatro y la cuarta se queda donde está.
3. Por qué solo una llega a cero
¿Qué tiene la lista con puntero al último que no
tienen las otras tres?
4. Cambiar de extremo no arregla nada
Las dos columnas del arreglo dan el mismo número.
¿Por qué?
Lo que quedó
La pila se construyó con un solo extremo y cualquiera de
las dos listas servía. La cola usa los dos, y ahí las implementaciones se
separan: el arreglo cobra Θ(n) en uno de los dos extremos, la enlazada
simple cobra Θ(n) al entrar por el final, y la enlazada que guarda el
último es la única donde los dos extremos caen sobre operaciones de Θ(1).
Encolar y desencolar n veces pasa de Θ(n²) a Θ(n).