Unidad 1 - emilioone05/Analisis_Algoritmos_utpl GitHub Wiki

📘 Unidad 1: Análisis de Algoritmos

Creado por Emilio Peña · Última edición reciente


🧭 Índice

  1. ¿Qué son los algoritmos?
  2. Conceptos de algoritmia
  3. Análisis empírico
  4. Análisis teórico de algoritmos
  5. Ejercicio en Python
  6. Ejercicio en Java
  7. Notaciones asintóticas
  8. Taller de clase

❓ ¿Qué son los algoritmos?

Un algoritmo es un conjunto de pasos bien definidos que permiten resolver un problema o realizar una tarea específica. En términos técnicos:

Un algoritmo es un conjunto de reglas para efectuar algún cálculo, bien sea a mano o, más frecuentemente, en una máquina.

Ejemplo de algoritmo


🧠 Conceptos de algoritmia

La algoritmia estudia las propiedades de los algoritmos y nos ayuda a elegir la solución más adecuada en cada situación.

  • Una buena elección puede ahorrar tiempo y recursos.
  • En algunos casos, una buena elección marca la diferencia entre poder resolver un problema y no poder hacerlo.

Ejemplo de multiplicación en diferentes países:

  • En Ecuador:

    Multiplicación en Ecuador

  • En Inglaterra:

    Multiplicación en Inglaterra

Aunque el proceso cambia, el resultado es el mismo. Esto demuestra que para problemas básicos pueden existir múltiples soluciones.


🧪 Análisis empírico

El análisis empírico evalúa el rendimiento de un algoritmo ejecutándolo en datos reales, en lugar de solo análisis teórico.

Ejemplo en Java:

public static long Suma(long n) {
    long Inicio = System.currentTimeMillis();
    long Resultado = 0;
    for (long i = 1; i < n; i++) {
        Resultado += i;
    }
    long Final = System.currentTimeMillis();
    long Total = Final - Inicio;
    System.out.println("Tiempo: " + Total + " ms");
    return Resultado;
}

Explicación:

  • Medición de Tiempo: Se utiliza System.currentTimeMillis() para medir el tiempo antes y después del bucle. La diferencia da el tiempo total en milisegundos.
  • Lógica de Suma: Suma todos los números desde 1 hasta n-1.
  • Salida: Imprime el tiempo de ejecución en la consola y retorna el resultado de la suma.

Desventajas del análisis empírico:

  • Es necesario implementar el algoritmo.
  • Los resultados pueden no ser indicativos para otras entradas.
  • Se requiere del mismo entorno para comparar dos algoritmos.

📊 Análisis teórico de algoritmos

El análisis teórico evalúa matemáticamente el rendimiento de algoritmos (tiempo/espacio) en función del tamaño de entrada (n).

Métricas clave:

  • Tiempo de ejecución (T(n)): Número de operaciones primitivas.
  • Principio de invariancia: Implementaciones distintas difieren solo por una constante multiplicativa.

Tipos de análisis:

  • Caso peor: Máximo tiempo posible (ej: ordenar un arreglo en orden inverso).
  • Caso mejor: Mínimo tiempo (ej: arreglo ya ordenado).
  • Caso promedio: Tiempo esperado para entradas aleatorias.

🐍 Ejercicio en Python

# Suma de 1 a n (Gauss)
def suma_gauss(n):
    return n * (n + 1) // 2  # O(1)

☕ Ejercicio en Java

Ejercicio en Java

public class MergeAlgorithm {

    public static void merge(int[] A, int p, int q, int r) {
        int nL = q - p + 1;
        int nR = r - q;
        int[] L = new int[nL];
        int[] R = new int[nR];

        for (int i = 0; i < nL; i++) {
            L[i] = A[p + i];
        }
        for (int j = 0; j < nR; j++) {
            R[j] = A[q + 1 + j];
        }

        int i = 0, j = 0, k = p;

        while (i < nL && j < nR) {
            if (L[i] <= R[j]) {
                A[k] = L[i];
                i++;
            } else {
                A[k] = R[j];
                j++;
            }
            k++;
        }

        while (i < nL) {
            A[k] = L[i];
            i++;
            k++;
        }

        while (j < nR) {
            A[k] = R[j];
            j++;
            k++;
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        int p = 0;
        int r = arr.length - 1;
        int q = (p + r) / 2;

        System.out.println("Arreglo original:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        merge(arr, p, q, r);

        System.out.println("\nArreglo después de MERGE:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

📐 Notaciones asintóticas

Las notaciones asintóticas permiten expresar la eficiencia de un algoritmo, proyectando el aumento de operaciones requeridas al aumentar el tamaño de la entrada.

Principales órdenes de complejidad:

  • O(1): Constante
  • O(log n): Logarítmica
  • O(n): Lineal
  • O(n log n): Cuasi lineal
  • O(n²): Cuadrática
  • O(2^n): Exponencial

Notaciones asintóticas


📝 Taller de clase

Resolución del taller


📚 Referencias