Introducción a estructuras de datos y algoritmos
En ciencias de la computación, las estructuras de datos y los algoritmos son la base fundamental para construir software eficiente y confiable. Son la caja de herramientas con la que los programadores resuelven problemas complejos, y determinan la velocidad de ejecución y el consumo de recursos de un programa.
Imagina que estás ordenando una estantería desordenada. Si simplemente apilas los libros al azar, encontrar un libro específico es muy difícil. Pero si ordenas por la primera letra del título o clasificas por categoría (como novela, historia, ciencia), la eficiencia de búsqueda mejora enormemente.Estructura de datoses como el método para organizar una estantería: define cómo deben organizarse y almacenarse los datos. Mientras queel algoritmoes el conjunto de pasos concretos para buscar, insertar o eliminar un libro.
Las estructuras de datos y los algoritmos son capacidades fundamentales de la informática, que se utilizan para resolver dos cosas: cómo organizar los datos y cómo resolver problemas de manera eficiente.
Estructura de datos
Estudia la forma de organizar los datos en la memoria o el almacenamiento, y cómo acceder a ellos y modificarlos de manera eficiente. Su objetivo principal es reducir el costo de tiempo y espacio.
Tipos comunes:
- Estructuras lineales: arreglos, listas enlazadas, pilas, colas
- Estructuras no lineales: árboles, grafos, montículos, tablas hash
Algoritmo
Estudia los pasos y estrategias para resolver problemas; en esencia, es una abstracción del proceso de cálculo. Solo hay dos criterios de evaluación: complejidad temporal y complejidad espacial.
Clasificación común:
- Algoritmos básicos: recorrido, recursión, divide y vencerás
- Ordenamiento y búsqueda: ordenamiento rápido, ordenamiento por mezcla, búsqueda binaria
- Estrategias avanzadas: voraz, programación dinámica, retroceso
Relación
La estructura de datos determina cómo almacenar; el algoritmo determina cómo calcular. Para un mismo problema, si la estructura cambia, la complejidad del algoritmo puede ser radicalmente diferente.
Estructura de datos
Una estructura de datos es la forma en que una computadora almacena y organiza los datos.
La estructura de datos tiene como objetivo implementar una colección de elementos de datos con una o más relaciones específicas, así como definir un conjunto de operaciones sobre esos datos.
Conceptos centrales
- Dato: Es un conjunto de símbolos que la computadora puede identificar, almacenar y procesar, como números, caracteres, etc.
- Elemento de dato: Es la unidad básica de los datos; en un programa generalmente se considera y se procesa como un todo.
- Ítem de dato: Es la unidad mínima que constituye un elemento de dato, con significado propio e indivisible.
- Estructura de datos: Es una colección de elementos de datos entre los cuales existen una o más relaciones específicas.
Clasificación de las estructuras de datos
Las estructuras de datos se dividen principalmente en dos grandes categorías:Estructura lógicayEstructura física。

Estructura lógicaDescribe las relaciones abstractas entre los elementos de datos, independientemente de cómo se implemente en la computadora. Se divide principalmente en:
- Estructura lineal: Existe una relación lineal "uno a uno" entre los elementos de datos. Por ejemplo, arreglos, listas enlazadas, pilas, colas.
- Estructura no lineal: Existen relaciones complejas "uno a muchos" o "muchos a muchos" entre los elementos de datos. Por ejemplo, árboles, grafos, conjuntos.
Estructura física(también llamada estructura de almacenamiento) describe la forma real en que los datos se almacenan en la memoria de la computadora. Se divide principalmente en:
- Almacenamiento secuencial: Almacena los elementos lógicamente adyacentes en unidades de almacenamiento cuyas posiciones físicas también son adyacentes. Por ejemplo, los arreglos.
- Almacenamiento encadenado: No requiere que los elementos lógicamente adyacentes estén físicamente adyacentes; las relaciones lógicas entre los elementos se representan mediante punteros adicionales. Por ejemplo, las listas enlazadas.
Algoritmo
Un algoritmo es una serie de pasos de instrucciones claros y finitos para resolver un problema específico.
Un algoritmo eficaz debe tener las siguientes cinco propiedades:
- Finitud: El algoritmo debe terminar después de ejecutar un número finito de pasos.
- Determinismo: Cada paso del algoritmo debe tener una definición exacta, sin ambigüedad.
- Viabilidad: Cada paso del algoritmo se puede realizar ejecutando un número finito de operaciones básicas ya implementadas.
- Entrada: Un algoritmo tiene cero o más entradas.
- Salida: Un algoritmo tiene una o más salidas; las salidas son cantidades que tienen una relación específica con las entradas.
Criterios de evaluación de algoritmos: complejidad temporal y complejidad espacial
¿Cómo juzgamos si un algoritmo es bueno? Por lo general, se evalúa desdeel tiempoyel espaciodos dimensiones.
- Complejidad temporal: Describe cualitativamente el tiempo de ejecución del algoritmo. Representa la tendencia de crecimiento del tiempo de ejecución a medida que aumenta el tamaño del problema n. Comúnmente se usa la notación O grande.
- Complejidad espacial: Describe cualitativamente el tamaño de espacio de almacenamiento temporal ocupado por el algoritmo durante su ejecución. También se expresa con la notación O grande.
Comparación de complejidades temporales comunes
La siguiente tabla muestra la tendencia de las diferentes complejidades temporales al crecer el tamaño de los datos:
| Representación de la complejidad | Nombre | Ejemplo (n=10 vs n=1000) | Descripción |
|---|---|---|---|
| O(1) | Orden constante | 1 paso vs 1 paso | La más eficiente, independiente del tamaño del problema |
| O(log n) | Orden logarítmico | ~3 pasos vs ~10 pasos | Muy eficiente, como la búsqueda binaria |
| O(n) | Orden lineal | 10 pasos vs 1000 pasos | Buena eficiencia, como recorrer un arreglo |
| O(n log n) | Orden lineal logarítmico | ~30 pasos vs ~10000 pasos | Eficiencia relativamente buena, como el ordenamiento rápido |
| O(n²) | Orden cuadrático | 100 pasos vs 1,000,000 pasos | Eficiencia baja, como el ordenamiento por selección simple |
| O(2ⁿ) | Orden exponencial | 1024 pasos vs una cifra astronómica | Eficiencia extremadamente baja, se debe evitar en lo posible |
Comprensión sencilla: Lo que buscamos es un algoritmo cuyo tiempo de ejecución crezca cada vez más lento a medida que el volumen de datos n aumenta. O(1) y O(log n) son excelentes, O(n) es aceptable, y O(n²) o superior requiere optimización cuando el volumen de datos es grande.
Ejemplos de estructuras de datos y algoritmos clásicos
Apliquemos las estructuras de datos y los algoritmos mediante un problema concreto.
Problema: En una lista de números desordenada, encontrar rápidamente si existe un número objetivo.
Solución 1: Búsqueda lineal (usando arreglos)
Este es un método intuitivo pero ineficiente.
- Estructura de datos: Arreglo (tabla lineal con almacenamiento secuencial).
- Algoritmo: Comenzar desde el primer elemento y comparar cada uno con el valor objetivo hasta encontrarlo o recorrer todos los elementos.
- Complejidad temporal: O(n). En el peor de los casos es necesario comprobar los n elementos.
Ejemplo
def linear_search(arr, target):
"""
Búsqueda lineal del valor objetivo target en el arreglo arr.
Parámetros:
arr: la lista a buscar
target: el valor objetivo a buscar
Retorna:
Si lo encuentra, retorna su índice; de lo contrario, retorna -1.
"""
for i in range(len(arr)): # Recorre cada elemento del arreglo
if arr[i] == target: # Si el elemento actual es igual al valor objetivo
return i # Retorna el índice actual
return -1 # Si termina el recorrido sin encontrarlo, retorna -1
# Datos de prueba
test_data = [12, 45, 67, 89, 34, 23, 90, 11]
target_number = 34
# Ejecuta la búsqueda
result = linear_search(test_data, target_number)
# Muestra el resultado
if result != -1:
print(f"El índice del número objetivo {target_number} en el arreglo es: {result}")
else:
print(f"No se encontró el número objetivo {target_number} en el arreglo")
Salida:
目标数字 34 在数组中的索引是:4
Solución 2: Búsqueda binaria (usando arreglos ordenados)
Este es un método eficiente, pero requiere que los datos estén ordenados.
- Estructura de datos: Arreglo ordenado.
- Algoritmo:
- Comparar el valor objetivo con el elemento central del arreglo.
- Si son iguales, lo ha encontrado.
- Si el valor objetivo es menor, repetir el paso 1 en la mitad izquierda del arreglo.
- Si el valor objetivo es mayor, repetir el paso 1 en la mitad derecha del arreglo.
- Si el intervalo de búsqueda está vacío, no se encontró.
- Complejidad temporal: O(log n). Cada comparación reduce el rango de búsqueda a la mitad.
Ejemplo
def binary_search(sorted_arr, target):
"""
Realiza una búsqueda binaria del valor objetivo target en el array ordenado sorted_arr.
Parámetros:
sorted_arr: lista ordenada (ascendente)
target: el valor objetivo a buscar
Devuelve:
Si se encuentra, devuelve su índice; de lo contrario, devuelve -1.
"""
left, right = 0, len(sorted_arr) - 1 # Inicializa el intervalo de búsqueda como todo el array
while left <= right: # Continúa buscando mientras el intervalo sea válido
mid = (left + right) // 2 # Calcula el índice central
if sorted_arr[mid] == target: # Valor objetivo encontrado
return mid
elif sorted_arr[mid] < target: # El valor objetivo está en la mitad derecha
left = mid + 1
else: # El valor objetivo está en la mitad izquierda
right = mid - 1
return -1 # Intervalo inválido, no encontrado
# Datos de prueba (deben estar ordenados)
test_data = [12, 45, 67, 89, 34, 23, 90, 11]
sorted_test_data = sorted(test_data) # Ordenar los datos de prueba
print(f"Array ordenado: {sorted_test_data}")
target_number = 34
# Ejecutar la búsqueda
result = binary_search(sorted_test_data, target_number)
# Mostrar resultado
if result != -1:
print(f"El índice del número objetivo {target_number} en el array ordenado es: {result}")
else:
print(f"No se encontró el número objetivo {target_number} en el array ordenado")
Resultado:
有序数组:[11, 12, 23, 34, 45, 67, 89, 90] 目标数字 34 在有序数组中的索引是:3
Comparación y reflexión:
- Cuando
n=1000En ese caso, la búsqueda lineal necesita como máximo 1000 comparaciones, mientras que la búsqueda binaria solo necesita alrededor de 10 comparaciones como máximo (porque 2^10 ≈ 1024). - La eficiencia de la búsqueda binaria es mucho mayor que la de la búsqueda lineal, pero requiere que los datos estén ordenados previamente. La ordenación en sí misma tiene un costo, por lo que la elección del algoritmo depende del escenario específico (por ejemplo, si los datos son estáticos y se buscan con frecuencia, o dinámicos y se insertan con frecuencia).
¿Cómo empezar a aprender?
Aprender estructuras de datos y algoritmos es un proceso gradual; se sugiere seguir la siguiente ruta:
- Dominar un lenguaje de programación: Primero necesitas una herramienta para implementar tus ideas; Python, Java o C++ son buenas opciones. Python tiene una sintaxis concisa, más adecuada para que los principiantes se centren en la lógica del algoritmo en sí.
- Empezar con estructuras de datos básicas:
- Array / Lista: La estructura de almacenamiento secuencial más básica y más utilizada.
- Listas enlazadas: La clave para entender punteros/referencias y asignación dinámica de memoria.
- Pilas y colas: Comprender las listas lineales con operaciones restringidas de "último en entrar, primero en salir" (LIFO) y "primero en entrar, primero en salir" (FIFO).
- Aprender ideas básicas de algoritmos:
- Algoritmos de ordenación: Ordenación de burbuja, ordenación por selección, ordenación por inserción (comprender O(n²)), luego aprender ordenación por mezcla (merge sort) y ordenación rápida (quick sort) (comprender O(n log n) y la idea de divide y vencerás).
- Algoritmos de búsqueda: Búsqueda secuencial, búsqueda binaria.
- Desafiar estructuras no lineales:
- árbol: Concéntrate en aprender árboles binarios, especialmente árboles binarios de búsqueda. Comprender los recorridos de árboles (preorden, inorden, postorden).
- grafo: Comprender las representaciones de grafos (matriz de adyacencia, lista de adyacencia) y algoritmos básicos de recorrido (búsqueda en profundidad DFS, búsqueda en amplitud BFS).
- Practicar y resolver problemas: Practica desde problemas simples en plataformas como LeetCode, Nowcoder, etc., aplicando la teoría a la práctica; esta es la mejor manera de consolidar conocimientos y entrenar el pensamiento.