Fundamentos de Estructuras de Datos y Algoritmia

En una célebre frase, el informático Niklaus Wirth tituló su libro más influyente:
$\mathbf{\text{Algoritmos}} + \mathbf{\text{Estructuras de Datos}} = \mathbf{\text{Programas}}$

Cualquier sistema de software, desde un sistema operativo hasta una red social o un motor de videojuegos, consiste fundamentalmente en organizar datos en la memoria del ordenador (Estructuras de Datos) y procesar esos datos siguiendo secuencias lógicas optimizadas (Algoritmos).

1. ¿Qué es un Algoritmo? #

Un algoritmo es un conjunto prescrito de instrucciones o reglas bien definidas, ordenadas, finitas y no ambiguas que permiten solucionar un problema o llevar a cabo una tarea de cómputo.

Propiedades Esenciales de un Algoritmo: #

1. Entrada y Salida: Recibe cero o más datos de entrada y produce un resultado concreto.
2. Finitud: Debe terminar obligatoriamente tras un número finito de pasos (no puede entrar en bucles infinitos no deseados).
3. Determinismo / Precisión: Para los mismos datos de entrada, cada paso debe estar definido sin ambigüedad y producir siempre el mismo resultado.
4. Eficacia: Cada instrucción debe ser lo suficientemente básica para poder ser ejecutada por la máquina en un tiempo razonable.

2. Estructuras de Datos Lineales #

1ARRAY (Memoria Contigua):            LISTA ENLAZADA (Nodos con Punteros):
2┌────┬────┬────┬────┐                ┌─────┬───┐    ┌─────┬───┐    ┌─────┬───┐
3│ 10 │ 20 │ 30 │ 40 │                │ 10  │ ──┼───►│ 20  │ ──┼───►│ 30  │null│
4└────┴────┴────┴────┘                └─────┴───┘    └─────┴───┘    └─────┴───┘
5Índice: 0    1    2    3
6
7PILA / STACK (LIFO - Último en entrar, primero en salir):
8Push ──► ┌─────┐
9         │  C  │ ◄── Top
10         ├─────┤
11         │  B  │
12         ├─────┤
13         │  A  │
14         └─────┘ ──► Pop
15
16COLA / QUEUE (FIFO - Primero en entrar, primero en salir):
17Enqueue (Entrada) ──► [ Elemento C ] [ Elemento B ] [ Elemento A ] ──► Dequeue (Salida)

3. Estructuras de Datos Asociativas y Jerárquicas #

Tablas Hash / Diccionarios / Mapas (Hash Tables) #

• Organizan la información en parejas de Clave $\rightarrow$ Valor ("usuario_123" -> {nombre: "Ana", edad: 28}).
• Utilizan una Función Hash matemática que transforma la clave alfanumérica en un índice numérico de memoria de forma instantánea.
• Ventaja: Búsqueda, inserción y borrado prácticamente instantáneos (Tiempo constante $O(1)$).

Árboles Binarios de Búsqueda (BST) #

• Estructura no lineal formada por nodos jerárquicos (raíz, ramas y hojas).
• Propiedad de orden: Para cualquier nodo, todos los elementos de su subárbol izquierdo son menores que él, y todos los de su subárbol derecho son mayores.

4. Algoritmos Clásicos: Búsqueda Lineal vs Búsqueda Binaria #

Supongamos que queremos encontrar si un número existe dentro de una lista de $1.000.000$ de elementos:

1BÚSQUEDA LINEAL: Comprueba uno por uno desde el principio
2[ 1 ][ 2 ][ 3 ][ 4 ] ... [ 999.999 ][ 1.000.000 ]  ──► Peor caso: 1.000.000 comparaciones
3
4BÚSQUEDA BINARIA: Divide el array ordenado por la mitad en cada paso
5Paso 1: Mira el elemento 500.000 ──► ¿Es mayor? Descarta los 500.000 inferiores
6Paso 2: Mira el elemento 750.000 ──► ¿Es menor? Descarta los 250.000 superiores
7...
8Máximo de pasos necesarios: log₂(1.000.000) ≈ 20 comparaciones

• Búsqueda Lineal: No requiere que la lista esté ordenada, pero su coste crece proporcionalmente al tamaño ($O(n)$).
• Búsqueda Binaria: Requiere que la lista esté previamente ordenada, pero reduce el problema a una complejidad logarítmica ($O(\log n)$), encontrando cualquier elemento entre un millón en un máximo de 20 preguntas.