La lista circular doble tiene n = 12 elementos.
Como la cadena se cierra y la lista guarda el contador, nodoEn(p)
puede salir de la cabeza hacia adelante o hacia atrás.
1. Los dos caminos hasta la posición 10
¿Cuántos pasos de frente hasta la posición 10?
¿Cuántos pasos por el lado corto?
2. Todas las posiciones
p
de frente
por el lado corto
sentido
El if (p <= n / 2) parte las posiciones en
dos mitades: en la primera se camina con siguiente desde la
cabeza, y en la segunda con anterior desde el último.
3. Recorrer las doce posiciones
Un programa pide obtener(p) una vez por
cada posición, de la 0 a la 11. ¿Cuántos pasos da en total cada versión?
Total de frente
Total por el lado corto
4. La cota de nodoEn
Escogiendo el lado, ¿en qué queda la cota de
nodoEn sobre una lista de n elementos?
Lo que quedó
El contador y el enlace hacia atrás compran escoger el
sentido: el peor caso baja de n - 1 pasos a ⌈n/2⌉ y el total de
un recorrido por posiciones baja casi a la mitad. La cota asintótica no se
mueve, porque ⌈n/2⌉ crece como n; lo que se gana es una
constante, y eso sí se mide en el reloj.