📌 ¿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²).

📌 1. Contando Operaciones Dominantes

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

Ejemplo: Sumar los primeros n números.

1public class SumNumbers {
2    public static int sum(int n) {
3        int total = 0;  // 1 operación
4        for (int i = 1; i <= n; i++) {  // n operaciones
5            total += i;  // n operaciones
6        }
7        return total;
8    }
9}

📌 Análisis:

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

📌 2. 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).

📌 3. 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.

1public class Search {
2    public static boolean find(int[] arr, int target) {
3        for (int num : arr) {
4            if (num == target) return true; // Se detiene si lo encuentra
5        }
6        return false;
7    }
8}

📌 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. Medición Práctica del Tiempo de Ejecución

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

1public class TimeMeasurement {
2    public static void main(String[] args) {
3        long start = System.nanoTime(); // Inicio del tiempo
4
5        int sum = 0;
6        for (int i = 0; i < 1000000; i++) {
7            sum += i;
8        }
9
10        long end = System.nanoTime(); // Fin del tiempo
11        System.out.println("Tiempo: " + (end - start) + " ns");
12    }
13}