Saltar al contenido
wandres.dev
Iniciar sesión

Recorrido narrado

Un caso completo

Sigue estas tres operaciones sobre un array con espacio para 6 valores, que empieza como [3, 8, 1]:

  1. leer(2): la cuenta da la dirección del tercer valor y devuelve 1. No se mira ningún otro valor.
  2. insertar(1, 6): el hueco va en la posición 1. Se corren 1 y 8 un lugar a la derecha, empezando por el 1. Queda [3, 6, 8, 1]: 2 desplazamientos.
  3. borrar(0): el hueco queda en la posición 0. Se corren 6, 8 y 1 un lugar a la izquierda, empezando por el 6. Queda [6, 8, 1]: 3 desplazamientos.

El patrón: leer o escribir una posición no depende de cuántos valores haya. Insertar o borrar en la posición i mueve todos los valores que están después de i.

En la figura están los cuatro estados del ejemplo; las flechas numeradas siguen el orden de los desplazamientos.

Leer, insertar y borrar en un array, paso a pasoCuatro pasos sobre un array con espacio para 6 valores. Paso 1: [3, 8, 1], longitud 3. Paso 2: leer(2) mira solo la posición 2 y devuelve 1. Paso 3: insertar(1, 6) corre el 1 de la posición 2 a la 3 y luego el 8 de la 1 a la 2, y escribe 6 en la 1; queda [3, 6, 8, 1], dos desplazamientos. Paso 4: borrar(0) corre el 6 de la posición 1 a la 0, el 8 de la 2 a la 1 y el 1 de la 3 a la 2; queda [6, 8, 1], tres desplazamientos.Paso 1 de 4: estado inicial, [3, 8, 1], longitud 3, capacidad 6381012345Paso 2 de 4: leer(2) mira solo la posición 2 y devuelve 1381012345Paso 3 de 4: insertar(1, 6) corre el 1 y el 8, empezando por el 138136*8*1*012345antesdespués12Paso 4 de 4: borrar(0) corre 6, 8 y 1 a la izquierda, desde el 636816*8*1*012345antesdespués123
Las flechas numeradas siguen el orden de los desplazamientos. Con * se marca lo recién escrito; borde grueso, lo que la operación mira.
Texto
función insertar(a, i, x):    para j desde longitud(a) − 1 hasta i, bajando:        a[j + 1] ← a[j]    a[i] ← x    longitud(a) ← longitud(a) + 1

Su fila en la tabla de costos

Esta es la fila del array en la tabla de costos de la ruta. Cada costo lleva su condición.

Representación leer(i) insertar o borrar al inicio insertar al final borrar al final insertar o borrar en i
array estático O(1) O(n), peor caso — (la capacidad es fija) O(1) O(n − i) desplazamientos; O(n) en el peor caso

Lee el recorrido de esta página. Al pasar al siguiente momento, este cuenta como leído.