Sensor[8] de tipo float. Dirección base 0x7FFF00,
4 bytes por elemento, memoria contigua. Escribe un índice y observa qué
hace realmente el procesador: una multiplicación y una suma. Nunca recorre.
Prueben el índice 8. La fórmula devuelve una dirección perfectamente válida.
¿Quién debe entonces detener el acceso: el lenguaje o el programador?
Leer cuesta lo mismo siempre. Abrir un hueco no. Para insertar en la posición 0, cada elemento posterior debe moverse una celda a la derecha. Cuenten los desplazamientos en el contador mientras corre la animación.
Inserten en la posición 0 y luego al final. Mismo arreglo, mismo valor, costo distinto. ¿Por qué agregar al final no mueve nada?
Mismo arreglo ordenado de 16 elementos, misma pregunta. La búsqueda lineal pregunta celda por celda. La binaria descarta la mitad en cada comparación. Corran las dos y comparen el contador.
Con 16 elementos la binaria necesita 4 comparaciones como máximo. Con un millón, ¿cuántas necesita? Pista: cada paso divide entre dos.
float Radar[3][3] se ve como una cuadrícula, pero la RAM es plana.
El compilador guarda fila por fila (row-major) y traduce cada par de índices con
i × M + j. Hagan clic en cualquier celda.
Los dos recorridos leen los mismos 9 elementos. El de columnas salta en la RAM y rompe la línea de caché. ¿Cuál de los dos ciclos anidados escribirían en un programa real?
La búsqueda binaria exige orden previo. Burbuja compara vecinos e intercambia; selección busca el mínimo de lo que falta. Los dos hacen del orden de n² comparaciones: lentos, pero fáciles de leer.
| Operación | Complejidad | Por qué |
|---|---|---|
Acceso A[i] | O(1) | Base + i × S. Una cuenta, sin recorrer. |
| Búsqueda lineal | O(n) | En el peor caso revisa las n celdas. |
| Búsqueda binaria | O(log n) | Descarta la mitad cada vez. Exige orden. |
| Insertar al inicio | O(n) | Mueve los n elementos posteriores. |
| Insertar al final | O(1) | Si hay espacio, no mueve nada. |
| Burbuja / selección | O(n²) | Ciclo dentro de ciclo sobre n elementos. |
Arreglo ordenado de 32 celdas con los valores tapados. Los dos equipos buscan el mismo objetivo, por turnos. Al inspeccionar una celda el juego solo responde mayor, menor o encontrado. Gana quien lo halle con menos inspecciones.
Inspeccionar el centro del rango vivo elimina la mitad de los candidatos, pase lo que pase. Cualquier otra celda elimina menos en el peor caso. Eso es búsqueda binaria: 32 celdas se resuelven en 6 inspecciones o menos, contra las 32 que puede costar revisarlas una por una.
Dir(A[i]) = Base + i × S. Por eso el acceso es O(1) y por eso el índice empieza en 0: el primer elemento tiene offset cero.Radar[2][3] compila y escribe en memoria ajena. El error es silencioso.i × M + j. Recorran por filas para aprovechar la caché.El arreglo es la estructura más rápida que existe para leer por posición, y la más rígida para cambiar de tamaño. Toda la materia que sigue — listas, pilas, colas, árboles — existe para negociar ese intercambio.