Análisis de Algoritmos

Un algoritmo es un conjunto de instrucciones bien definidas, ordenadas y finitas para resolver un problema paso a paso. Similar a una receta de cocina, recibe una entrada, procesa y produce un resultado. No basta con que funcione: dos algoritmos pueden resolver lo mismo, pero uno puede ser mucho más rápido o consumir menos memoria que el otro.

Cuando analizamos algoritmos, nos enfocamos en dos recursos críticos: el Tiempo (cuánto tarda en ejecutarse) y el Espacio (cuánta memoria extra necesita). Nuestro objetivo es estimar cómo crecen estos recursos a medida que aumenta el tamaño de la entrada.

La complejidad temporal mide el número de operaciones básicas que realiza un algoritmo en función de "n" (tamaño de la entrada). No medimos segundos exactos, sino el orden de crecimiento (lineal, cuadrático, etc.).

int sumarElementos(int arr[], int n) {
    int suma = 0;
    for (int i = 0; i < n; i++) {
        suma += arr[i]; // Operación que se repite n veces
    }
    return suma;
}
// Complejidad: O(n)

int sumarElementos(int arr[], int n) {
    int suma = 0;
    for (int i = 0; i < n; i++) {
        suma += arr[i]; // Operación que se repite n veces
    }
    return suma;
}
// Complejidad: O(n)

La complejidad espacial mide la memoria auxiliar requerida. Si un algoritmo solo usa variables simples, es O(1) (espacio constante). Si necesita duplicar un arreglo de tamaño n, es O(n) (espacio lineal).

int* copiarInvertido(int arr[], int n) {
    // Reserva memoria nueva proporcional a n
    int* invertido = malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        invertido[i] = arr[n - 1 - i];
    }
    return invertido;
}
// Complejidad Espacial: O(n)

int* copiarInvertido(int arr[], int n) {
    // Reserva memoria nueva proporcional a n
    int* invertido = malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        invertido[i] = arr[n - 1 - i];
    }
    return invertido;
}
// Complejidad Espacial: O(n)

Big-O es la notación estándar para describir la eficiencia asintótica. Nos permite clasificar algoritmos ignorando constantes y detalles de hardware, enfocándonos en el término dominante (el que más pesa cuando n es grande).

Imagen 11. Notación Big-O

Representación visual de los componentes de la complejidad computacional: Tiempo y Espacio.

Las clases más comunes de menor a mayor costo son: - O(1): Constante (acceso a array). - O(log n): Logarítmica (búsqueda binaria). - O(n): Lineal (recorrer una lista). - O(n log n): Lineal-logarítmica (ordenamiento eficiente). - O(n²): Cuadrática (bucles anidados).

Imagen 12. Crecimiento de las funciones de complejidad

Gráfica comparativa del crecimiento de funciones: observa cómo O(n²) se dispara rápidamente comparado con O(n) o O(log n).

Al analizar un algoritmo teóricamente, distinguimos tres escenarios: - Peor caso (Big-O): El escenario más desfavorable. Es el más importante porque nos da garantías. - Mejor caso: Escenario ideal (ej. encontrar el dato en la primera posición). - Caso promedio: El comportamiento esperado con entradas típicas.

Mientras el análisis teórico (Big-O) predice el comportamiento, el análisis empírico consiste en medir tiempos reales de ejecución (benchmarking) con distintas entradas. Ambos son necesarios: la teoría guía el diseño y la práctica verifica el rendimiento real en el hardware específico.