9. Análisis de Complejidad

#estructuraDeDatos #universidad

El análisis de complejidad es una disciplina que permite evaluar la eficiencia de los algoritmos en términos de tiempo y espacio. Es fundamental para determinar la viabilidad de un algoritmo, especialmente cuando se trabaja con grandes conjuntos de datos.

a. Nomenclatura de Representación

La nomenclatura asintótica se utiliza para describir el comportamiento del tiempo de ejecución o el uso de espacio de un algoritmo en función del tamaño de la entrada. Las principales notaciones son:

1. Notación O Grande (Big O):

   • Descripción: Representa el límite superior del tiempo de ejecución. Indica la peor complejidad posible.
   • Ejemplo: Un algoritmo con complejidad O(n²) tiene un tiempo de ejecución que crece proporcionalmente al cuadrado del tamaño de la entrada.

2. Notación Ω (Omega):

   • Descripción: Representa el límite inferior del tiempo de ejecución. Indica la mejor complejidad posible.
   • Ejemplo: Un algoritmo con complejidad Ω(n) tiene un tiempo de ejecución que, en el mejor de los casos, crece linealmente con el tamaño de la entrada.

3. Notación Θ (Theta):

   • Descripción: Representa una cota ajustada. Indica que el tiempo de ejecución crece de manera asintótica tanto en el límite superior como inferior.
   • Ejemplo: Un algoritmo con complejidad Θ(n log n) tiene un tiempo de ejecución que crece proporcionalmente a n log n en el mejor y peor de los casos.

Comparación de Notaciones:

b. Herramientas de Análisis

Para realizar un análisis de complejidad, se utilizan diversas herramientas y técnicas que permiten evaluar cómo se comporta un algoritmo a medida que crece el tamaño de la entrada.

1. Análisis Asintótico:

• Descripción: Estudia el comportamiento del algoritmo cuando el tamaño de la entrada tiende a infinito.
• Objetivo: Determinar la complejidad en términos de notaciones asintóticas (Big O, Omega, Theta).

2. Recurrencias:

• Descripción: Son ecuaciones que definen una secuencia de valores basados en sus valores previos.
• Uso: Comúnmente utilizadas para analizar algoritmos recursivos.
• Ejemplo: La recurrencia de Merge Sort es T(n) = 2T(n/2) + O(n).

3. Diagramas de Flujo y Pseudocódigo:

• Descripción: Ayudan a visualizar el flujo de un algoritmo y a identificar los bucles y llamadas recursivas que impactan la complejidad.
• Uso: Facilitan la identificación de patrones que determinan la complejidad.

4. Tabla de Tiempos de Ejecución:

• Descripción: Consiste en medir el tiempo de ejecución real del algoritmo para diferentes tamaños de entrada.
• Uso: Aunque no reemplaza el análisis teórico, proporciona una visión práctica del rendimiento.

5. Análisis Empírico:

• Descripción: Involucra implementar el algoritmo y medir su desempeño en entornos reales.
• Uso: Complementa el análisis asintótico para validar la eficiencia en casos prácticos.

Ejemplo de Análisis de Complejidad:

Algoritmo de Búsqueda Lineal:

int busquedaLineal(int arr[], int n, int x) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == x)
            return i; // Tiempo constante O(1)
    }
    return -1; // Tiempo constante O(1)
}

Análisis de Complejidad:

• Peor Caso: El elemento no está en el arreglo o está al final. Se realizan n comparaciones.
  • Big O: O(n)
• Mejor Caso: El elemento está en la primera posición. Se realiza 1 comparación.
  • Omega: Ω(1)
• Caso Promedio: El elemento está en una posición aleatoria.
  • Theta: Θ(n)

Ejercicios

p

1. Determinar la Complejidad de un Algoritmo:

   • Analiza el siguiente fragmento de código y determina su complejidad en Big O:

void ejemplo(int n) {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            printf("*");
        }
    }
}  

- Respuesta Esperada: O(n²)
2. Recurrencias y Su Solución:

- Resuelve la siguiente recurrencia usando el teorema maestro:

T(n) = 2T(n/2) + O(n)

- Respuesta Esperada: T(n) = O(n log n)
3. Comparación de Complejidades:

- Ordena los siguientes algoritmos de menor a mayor complejidad:

- O(1)
- O(n log n)
- O(n²)
- O(log n)
- O(n)
- Respuesta Esperada: O(1) < O(log n) < O(n) < O(n log n) < O(n²)

4. Optimización de Algoritmos:

   • Dado un algoritmo con complejidad O(n²), describe una estrategia para optimizarlo y reducir su complejidad.
   • Respuesta Esperada: Identificar bucles anidados y buscar formas de eliminar redundancias, posiblemente aplicando un algoritmo más eficiente como Quick Sort o Merge Sort, que tienen una complejidad de O(n log n).