Medición del Rendimiento Algorítmico

1. Cómo medir la complejidad de un algoritmo? #

Para analizar la eficiencia de un algoritmo, debemos contar cuántas operaciones realiza en función del tamaño de la entrada n.

Ejemplo:

• Si un algoritmo ejecuta una sola operación, su tiempo de ejecución es O(1).
• Si recorre n elementos en un bucle, su tiempo de ejecución es O(n).
• Si usa dos bucles anidados, su tiempo de ejecución es O(n²).

2. 2. Contando Operaciones Dominantes #

Cuando medimos la complejidad, solo nos interesa la operación más costosa.

Ejemplo: Sumar los primeros n números.

📌 Análisis:

• El bucle se ejecuta n veces.
• La operación de suma se ejecuta n veces.
• La complejidad es O(n).

3. 3. Ignorar Constantes y Términos No Dominantes #

Cuando analizamos un algoritmo, ignoramos las constantes porque no afectan el crecimiento para valores grandes de n.

Ejemplo:

1public int example(int n) {
2    int x = 10; // O(1)
3    for (int i = 0; i < n; i++) {  // O(n)
4        System.out.println(i);
5    }
6    return x;
7}

• La operación int x = 10; es constante O(1).
• El bucle es O(n).
• Conclusión: O(n) domina, por lo que el algoritmo es O(n).

4. 4. Casos Peor, Mejor y Promedio #

El rendimiento de un algoritmo depende del caso en el que se ejecuta.

Ejemplo: Búsqueda de un número en un array.

📌 Análisis:

• Mejor caso: O(1) si el número está al inicio.
• Peor caso: O(n) si el número está al final o no está en el array.
• Caso promedio: O(n/2), pero ignoramos la constante 1/2, por lo que sigue siendo O(n).

5. 5. Medición Práctica del Tiempo de Ejecución #

Para medir el tiempo real de ejecución, usamos funciones de temporización.