SEMANA_06_B1 - meruiz22/Analisis-de-Algoritmos GitHub Wiki

3. Análisis de Algoritmos

El análisis de algoritmos evalúa el rendimiento de un algoritmo en términos de tiempo (complejidad temporal) y espacio (complejidad espacial) requeridos para resolver un problema. Este análisis es esencial para comparar soluciones y elegir la más eficiente, especialmente en aplicaciones donde el rendimiento es crítico, como bases de datos o sistemas en tiempo real.

Introducción al Análisis de Algoritmos

El análisis de algoritmos mide cuánto tiempo y memoria necesita un algoritmo en función del tamaño de la entrada (n). Esto permite predecir su comportamiento con datos grandes y optimizar recursos.

Importancia

  • Predice el rendimiento para entradas grandes.
  • Facilita la comparación objetiva entre algoritmos.
  • Es clave para diseñar sistemas escalables y eficientes.

Complejidad Temporal

La complejidad temporal mide el tiempo de ejecución de un algoritmo, expresado mediante notación asintótica.

Notación Asintótica

  • Big O (O): Límite superior, describe el peor caso.
  • Omega (Ω): Límite inferior, describe el mejor caso.
  • Theta (Θ): Crecimiento exacto, cuando mejor y peor caso son similares.

Mejor, Peor y Caso Promedio

  • Mejor caso: Entrada que minimiza el tiempo, por ejemplo, el elemento en la primera posición en búsqueda lineal (O(1)).
  • Peor caso: Entrada que maximiza el tiempo, por ejemplo, elemento no presente en búsqueda lineal (O(n)).
  • Caso promedio: Tiempo esperado para entradas aleatorias, por ejemplo, O(n) en búsqueda lineal.

Ejemplos

Algoritmo Mejor Caso Peor Caso Caso Promedio
Búsqueda Lineal O(1) O(n) O(n)
Búsqueda Binaria O(1) O(log n) O(log n)
Ordenamiento por Burbuja O(n) O(n^2) O(n^2)
Ordenamiento por Mezcla O(n log n) O(n log n) O(n log n)

Ejemplo en Pseudocódigo

Búsqueda Lineal:

PROCEDURE Buscar(a: vector; c: INTEGER): INTEGER;
VAR j: INTEGER;
BEGIN
    j := 1;                     // O(1)
    WHILE j <= n AND a[j] ≠ c DO  // Hasta n iteraciones
        j := j + 1;             // O(1) por iteración
    END;
    IF j <= n THEN              // O(1)
        RETURN j;
    ELSE
        RETURN 0;
    END;
END;

Análisis: En el peor caso, el bucle se ejecuta n veces, dando una complejidad de O(n).

Complejidad Espacial

La complejidad espacial mide la memoria requerida por un algoritmo, incluyendo variables auxiliares y estructuras de datos.

Ejemplos

  • Búsqueda lineal: O(1) – usa pocas variables.
  • Ordenamiento por mezcla (Merge Sort): O(n) – necesita espacio adicional para combinar listas.
  • Quick Sort: O(log n) – por la pila de recursión en promedio.

Estructuras de Control

Las estructuras de control determinan el flujo de ejecución de un algoritmo, afectando directamente su complejidad temporal y espacial.

Tipos de Estructuras de Control

  • Secuenciales: Instrucciones ejecutadas en orden (e.g., asignaciones simples).
  • Condicionales: Ejecutan bloques según condiciones (e.g., if-else, switch).
  • Iterativas: Repiten código (e.g., bucles for, while).
  • Recursivas: Funciones que se llaman a sí mismas (e.g., factorial).

Análisis de Estructuras de Control

  • Secuenciales: Suma de operaciones, usualmente O(1) por instrucción.
  • Condicionales: Complejidad es el máximo de las ramas, e.g., O(max(T_A, T_B)).
  • Iterativas: Depende del número de iteraciones, e.g., un bucle de n iteraciones es O(n).
  • Recursivas: Se analizan con relaciones de recurrencia, e.g., el factorial recursivo es O(n).

Ejemplos

Estructura Ejemplo Complejidad Temporal
Secuencial Sumar dos números (a = b + c) O(1)
Condicional if-else para comparar valores O(1)
Iterativa Bucle for de 1 a n O(n)
Anidada Dos bucles for de 1 a n O(n^2)
Recursiva Calcular factorial O(n)

Referencias