Fundamentos de algoritmos y métodos de análisis

En el mundo de la informática,algoritmoes la receta de la computadora: una secuencia de instrucciones definida, finita y ejecutable, utilizada para resolver un problema específico o realizar una tarea de cálculo concreta. Ya sea la aplicación de navegación del teléfono que planifica la ruta más corta para ti, o el motor de búsqueda que encuentra las páginas web más relevantes entre una enorme cantidad de datos en milisegundos, todo ello depende de algoritmos cuidadosamente diseñados.

Comprender los fundamentos de los algoritmos y los métodos de análisis es un paso clave para que todo programador pase de ser un implementador de código a un solucionador de problemas.

Este artículo te guiará para conocer sistemáticamente los conceptos centrales de los algoritmos y aprender a evaluar científicamente la calidad de un algoritmo.

Características principales de los algoritmos

Un algoritmo calificado debe poseer las siguientes cinco características básicas; podemos entenderlas con una analogía de cocina:

  1. Finitud: el algoritmo debe terminar después de ejecutar un número finito de pasos. Así como una receta no puede pedirte que remuevas infinitamente hasta el fin del universo, debe dar una condición de parada clara.
  2. Determinismo: cada paso del algoritmo debe tener una definición exacta, sin ambigüedad. Por ejemplo, 'añadir un poco de sal' es indeterminado, mientras que 'añadir 5 gramos de sal' es determinado.
  3. Factibilidad: cada operación del algoritmo debe ser básica y ejecutable. No puedes escribir en una receta 'bate los huevos con el poder de la mente'.
  4. Entrada: un algoritmo tiene cero o más entradas. Estas entradas son los objetos que el algoritmo procesa, como los ingredientes que necesita una receta.
  5. Salida: un algoritmo tiene una o más salidas. Las salidas son cantidades que tienen una relación específica con las entradas y son el resultado de la ejecución del algoritmo, como el plato final preparado.

¿Cómo describir un algoritmo?

Podemos describir un algoritmo de varias maneras; las más comunes son tres:

1. Descripción en lenguaje natural

Narrar los pasos del algoritmo en lenguaje humano (como chino o inglés). La ventaja es que es fácil de entender, pero la desventaja es que no es lo suficientemente preciso y puede generar ambigüedad.

Ejemplo: encontrar el mayor de tres números.

  1. Compara el primer número con el segundo y recuerda el mayor.
  2. Compara el número recordado en el paso anterior con el tercer número.
  3. Muestra el número mayor como el máximo.

2. Diagrama de flujo

Utiliza símbolos gráficos para representar el flujo de control del algoritmo. Muestra de manera intuitiva las relaciones lógicas entre los pasos.

Explicación del diagrama de flujo: esta figura muestra claramente el proceso de decisión del algoritmo para encontrar el máximo de tres números. El rombo representa una decisión condicional, el rectángulo representa un paso de procesamiento y las flechas indican la dirección de ejecución del programa.

3. Pseudocódigo

Una forma de descripción intermedia entre el lenguaje natural y el lenguaje de programación. Utiliza estructuras similares a las de los lenguajes de programación (comoif, for, while), pero ignora los detalles sintácticos específicos y se centra en la expresión lógica.

算法：FindMax
输入：三个数字 a, b, c
输出：最大值 max

1.  if a > b then
2.      max = a
3.  else
4.      max = b
5.  end if
6.  if c > max then
7.      max = c
8.  end if
9.  输出 max

4. Implementación en lenguaje de programación

Finalmente, el algoritmo debe traducirse a código en algún lenguaje de programación (como Python, Java, C++) para poder ejecutarse en una computadora.

Ejemplo

# Implementación en Python: encontrar el mayor de tres números
def find_max(a, b, c):
    # Primero compara a y b, asigna el mayor a max_value
    if a > b:
        max_value = a
    else:
        max_value = b
    # Luego compara max_value con c
    if c > max_value:
        max_value = c
    return max_value

# Código de prueba
print(find_max(5, 9, 3))  # Salida: 9
print(find_max(-1, 0, 1)) # Salida: 1

Resultado de salida:

9
1

Análisis de algoritmos: ¿Cómo evaluar la calidad de un algoritmo?

Diseñar un algoritmo que resuelva el problema es solo el primer paso; también necesitamos juzgar cuál algoritmo es mejor. Normalmente lo evaluamos desde dos dimensiones:

1. Complejidad temporal

Mide cómoel tiempo necesario para ejecutar el algoritmocrece a medida queel tamaño de los datos de entrada (n)aumenta. No nos centramos en el número concreto de segundos, sino en la tendencia de crecimiento (denominadacomplejidad temporal asintótica）。

Comparación de complejidades temporales comunes:

Complejidad Nombre Ejemplo (n=cantidad de datos) Metáfora ilustrativa
O(1) Orden constante Acceso a un elemento de un array por índice Encender la luz. No importa lo grande que sea la habitación, el tiempo de pulsar el interruptor es el mismo.
O(log n) Orden logarítmico Búsqueda binaria Buscar en un diccionario. Cada vez se descarta la mitad, la búsqueda es muy rápida.
O(n) Orden lineal Recorrer un array Contar personas. Se cuenta persona por persona, el tiempo es proporcional al número total de personas.
O(n log n) Orden lineal-logarítmico Ordenamiento rápido, ordenamiento por mezcla Ordenamiento de divide y vencerás. Es mucho más rápido que O(n²).
O(n²) Orden cuadrático Ordenamiento por selección simple, ordenamiento de burbuja Darse la mano de dos en dos. Cada persona debe darse la mano con todas las demás una vez.
O(2ⁿ) Orden exponencial Resolver la Torre de Hanói, enumeración exhaustiva por fuerza bruta División celular. El crecimiento es terrible; un n ligeramente grande resulta insoportable.

¿Cómo analizar?Presta atención a los bucles y la recursión.

  • Bucle simple: normalmente O(n).
  • Bucles anidados: normalmente O(n²) (si ambos niveles están relacionados con n).
  • Estrategia de bisección: normalmente O(log n).

2. Complejidad espacial

Mide cómoel espacio de memoria necesario para ejecutar el algoritmocrece a medida queel tamaño de los datos de entrada (n)aumenta. Además de almacenar los propios datos de entrada, también hay que considerar los arrays, variables, etc., que se solicitan adicionalmente durante la ejecución del algoritmo.

Análisis de ejemplo:

Ejemplo

# Ejemplo 1: complejidad espacial O(1)
def find_max_in_list(lst):
    max_val = lst[0]          # Solo se utilizan un número constante de variables adicionales
    for num in lst:
        if num > max_val:
            max_val = num
    return max_val

# Ejemplo 2: complejidad espacial O(n)
def copy_and_double_list(lst):
    new_list = []             # Se crea una nueva lista de la misma longitud que la lista de entrada
    for num in lst:
        new_list.append(num * 2)
    return new_list

Práctica: análisis y aplicación con algoritmos de ordenamiento

Tomemos el clásicoordenamiento de burbujacomo ejemplo para aplicar de forma integral los conocimientos anteriores.

Idea del algoritmo

Recorre repetidamente la lista que se va a ordenar, comparando una vez dos elementos adyacentes; si están en el orden incorrecto, los intercambia.

El recorrido por la lista se repite hasta que no haya elementos que necesiten intercambiarse, lo que significa que la lista está ordenada. Los elementos más pequeños van subiendo gradualmente como burbujas hasta la parte superior de la secuencia.

Implementación en Python y explicación línea por línea

Ejemplo

def bubble_sort(arr):
    """
Algoritmo de ordenamiento de burbuja
Parámetro arr: la lista a ordenar
Valor de retorno: la lista ordenada (modificada in situ, también se devuelve directamente)
    """
    n = len(arr)
    # Bucle externo: controla cuántas rondas de 'burbujeo' se necesitan en total
    for i in range(n - 1):
        # Se supone que esta ronda ya está ordenada, para optimizar
        swapped = False
        # Bucle interno: realiza una ronda de burbujeo, 'hunde' el elemento más grande al final
        # Después de cada ronda, los últimos i+1 elementos están ordenados, por lo que el rango es n-1-i
        for j in range(0, n - 1 - i):
            # Si el elemento anterior es mayor que el posterior, se intercambian
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]  # Elegante sintaxis de intercambio de Python
                swapped = True  # Se ha producido un intercambio
        # Si en esta ronda no se ha producido ningún intercambio, significa que la lista está completamente ordenada y se termina antes
        if not swapped:
            break
    return arr

# Datos de prueba y verificación
test_data = [64, 34, 25, 12, 22, 11, 90]
print("Antes de ordenar:", test_data)
sorted_data = bubble_sort(test_data.copy()) # Usa copy para evitar que la lista original sea modificada
print("Después de ordenar:", sorted_data)

# Verifica si el resultado es correcto
print("¿La ordenación es correcta?", sorted_data == sorted(test_data.copy())) # Debería coincidir con el resultado de ordenación integrado de Python

Resultado de salida:

排序前: [64, 34, 25, 12, 22, 11, 90]
排序后: [11, 12, 22, 25, 34, 64, 90]
排序是否正确? True

Análisis del algoritmo

  • Complejidad temporal：
    • Caso peor y promedio O(n²): cuando la lista está completamente en orden inverso, se necesitan(n-1) + (n-2) + ... + 1 = n(n-1)/2comparaciones e intercambios.
    • Mejor caso O(n): cuando la lista ya está ordenada, al añadirswappedla optimización de la bandera, basta con recorrerla una vez para comprobar que no hay intercambios y terminar antes.
  • Complejidad espacial O(1): el algoritmo solo utilizai, j, swappedcomo una cantidad fija de variables temporales, esordenación in situalgoritmo.

Tarea de práctica

  • Simulación manual: usa papel y lápiz para seguir el algoritmo, ordena la lista[5, 3, 8, 1]y escribe el estado de la lista después de cada pasada de burbuja.
  • Experimento de complejidad: modifica los datos de prueba, usando respectivamente una lista ya ordenada (por ejemplo,[1,2,3,4,5]) y una lista completamente en orden inverso (por ejemplo,[5,4,3,2,1]) para probar, observa el número de iteraciones (puedes añadir un contador en el bucle interno).
  • Intenta mejorar: ¿Puedes pensar en un algoritmo de ordenación similar a la idea del burbujeo, pero posiblemente más eficiente? (Pista: en cada recorrido no solo sube una burbuja máxima, sino que también baja una burbuja mínima).
Otras extensiones