Al resolver problemas complejos o manejar grandes volúmenes de datos con un ordenador, surge inevitablemente la inquietud sobre el rendimiento del software.

El estudio de la eficiencia de un algoritmo se fundamenta en un enfoque sistemático, similar al método científico. Este proceso permite establecer modelos matemáticos conicsos que predicen el comportamiento de un programa, los cuales se validan posteriormente con datos experimentales.

Modelo de Análisis

Para caracterizar el tiempo de ejecución, se identifica una operación elemental que se ejecuta con mayor frecuencia, denominada el ciclo interno. La clave es determinar cuántas veces se realiza esta operación en función del tamaño de la entrada. Un algoritmo con un ciclo anidado triple, como el que busca ternas que sumen cero, suele presentar un crecimiento cúbico.

public class BusquedaTerna {
    public static int contar(int[] datos) {
        int longitud = datos.length;
        int contador = 0;
        for (int idxA = 0; idxA < longitud; idxA++) {
            for (int idxB = idxA + 1; idxB < longitud; idxB++) {
                for (int idxC = idxB + 1; idxC < longitud; idxC++) {
                    if (datos[idxA] + datos[idxB] + datos[idxC] == 0) {
                        contador++;
                    }
                }
            }
        }
        return contador;
    }
}

Las matemáticas proporcionan modelos de crecimiento que categorizan la eficiencia de un algoritmo, siendo los más comunes:

• Constante - O(1)
• Logarítmico - O(log N)
• Lineal - O(N)
• Linealítmico - O(N log N)
• Cuadrático - O(N²)
• Cúbico - O(N³)
• Exponencial - O(2N)

Estrategias de Optimización

La clave para mejorar un algoritmo reside en reducir el orden de complejidad del ciclo interno. Para el problema de las ternas (3-sum), una aproximación más eficiente se basa en combinar ordenamiento y búsqueda binaria.

Primero, se puede resolver el caso más simple de buscar pares que sumen cero (2-sum) de manera óptima.

import java.util.Arrays;

public class ParSumaRapido {
    public static int contar(int[] arreglo) {
        Arrays.sort(arreglo);
        int n = arreglo.length;
        int total = 0;
        for (int i = 0; i < n; i++) {
            int complemento = -arreglo[i];
            int posicion = Arrays.binarySearch(arreglo, complemento);
            // Verificar que el complemento exista y su índice sea mayor
            if (posicion > i) {
                total++;
            }
        }
        return total;
    }
}

Extendiendo este principio, se puede construir una solución para el 3-sum con complejidad O(N² log N).

import java.util.Arrays;

public class TernaSumaRapida {
    public static int contar(int[] datos) {
        Arrays.sort(datos);
        int total = 0;
        int n = datos.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int sumaPar = datos[i] + datos[j];
                int objetivo = -sumaPar;
                // Buscar el objetivo en la porción restante del arreglo
                if (Arrays.binarySearch(datos, j + 1, n, objetivo) >= 0) {
                    total++;
                }
            }
        }
        return total;
    }
}

La tarea del análisis es descubrir propiedades fundamentales de los algoritmos, miantras que la del desarrollador es aplicar ese conocimiento para crear soluciones eficientes y robustas. Los algoritmos clásicos son valiosos porque ofrecen garantías teóricas sólidas sobre su rendimiento.