Análisis de Complejidad Algorítmica

Referencias y Lecturas Complementarias¶

Introducción¶

Desarrollo¶

Introducción: El Estudio de la Eficiencia¶

El análisis de algoritmos es una disciplina fundamental en la ciencia de la computación que se enfoca en cuantificar los recursos que un algoritmo consume. Su propósito es predecir, de manera formal y rigurosa, cómo se comportará un algoritmo en términos de tiempo de ejecución y uso de memoria a medida que el tamaño de la entrada de datos crece.

El objetivo principal no es obtener tiempos exactos en segundos —una métrica volátil que depende del hardware, el compilador y el sistema operativo— sino establecer una base teórica para:

1. Comparar algoritmos: Determinar objetivamente cuál de dos algoritmos es más eficiente para resolver un mismo problema.

2. Predecir la escalabilidad: Entender si un algoritmo seguirá siendo viable cuando el volumen de datos aumente de miles a millones o miles de millones de registros.

3. Optimizar el código: Identificar los cuellos de botella y las partes críticas de un programa que más impactan en su rendimiento.

Para lograr esto, la herramienta central es el análisis asintótico.

Análisis Asintótico: Enfocándose en lo que Importa¶

El análisis asintótico es una metodología matemática que describe el comportamiento de una función en su límite, es decir, cuando el tamaño de la entrada ($n$) se vuelve arbitrariamente grande (tiende al infinito). Este enfoque nos permite abstraernos de los detalles de la implementación y del hardware, y concentrarnos en la tasa de crecimiento intrínseca del algoritmo.

Al analizar una función de costo como $T(n) = 3n^2 + 100n + 500$, observamos que para valores grandes de $n$, el término $3n^2$ domina a los demás. El análisis asintótico nos permite simplificar esta expresión a su orden de crecimiento, que es $n^2$, ignorando constantes multiplicativas (3) y términos de menor orden ($100n + 500$).

Las Notaciones Asintóticas: O, Ω, y Θ¶

Para formalizar este análisis, utilizamos un conjunto de notaciones que describen los límites del crecimiento de la función de costo de un algoritmo.

1. Notación Big O (O) - Cota Superior (Peor Caso)¶

La notación Big O es la más utilizada en la práctica, ya que describe una cota superior asintótica. Nos ofrece una garantía sobre el rendimiento del algoritmo: nunca será peor que esta cota.

• Definición Intuitiva: Una función $f(n)$ pertenece a $O(g(n))$ si su tasa de crecimiento es igual o más lenta que la de $g(n)$ para entradas suficientemente grandes.

• Definición Formal: $f(n) \in O(g(n))$ si existen constantes positivas $c$ y $n_0$ tales que $0 \le f(n) \le c \cdot g(n)$ para todo $n \ge n_0$.

• Uso Práctico: Representa el peor caso de ejecución de un algoritmo.

2. Notación Omega (Ω) - Cota Inferior (Mejor Caso)¶

La notación Omega describe una cota inferior asintótica. Nos garantiza que el rendimiento del algoritmo nunca será mejor que esta cota.

• Definición Intuitiva: Una función $f(n)$ pertenece a $\Omega(g(n))$ si su tasa de crecimiento es igual o más rápida que la de $g(n)$.

• Definición Formal: $f(n) \in \Omega(g(n))$ si existen constantes positivas $c$ y $n_0$ tales que $0 \le c \cdot g(n) \le f(n)$ para todo $n \ge n_0$.

• Uso Práctico: Representa el mejor caso de ejecución.

3. Notación Theta (Θ) - Cota Ajustada (Caso Exacto)¶

La notación Theta proporciona la descripción más precisa del comportamiento de un algoritmo, acotándolo tanto por arriba como por abajo.

• Definición Intuitiva: Una función $f(n)$ pertenece a $\Theta(g(n))$ si su tasa de crecimiento es exactamente la misma que la de $g(n)$.

• Relación: $f(n) \in \Theta(g(n))$ si y solo si $f(n) \in O(g(n))$ y $f(n) \in \Omega(g(n))$.

• Uso Práctico: Describe el comportamiento del algoritmo de forma ajustada, a menudo representando el caso promedio o un escenario donde el mejor y el peor caso coinciden.

Notaciones Menos Comunes¶

Little-o (Límite Asintótico Estricto)¶

$f(n) \in o(g(n))$ si para toda constante $c > 0$, existe $n_0$ tal que:

Equivalentemente: $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$

Ejemplo: $n \in o(n^2)$ pero $n \notin o(n)$

Little-omega (Límite Inferior Estricto)¶

$f(n) \in \omega(g(n))$ si para toda constante $c > 0$, existe $n_0$ tal que:

Propiedades Algebraicas¶

Las notaciones asintóticas tienen propiedades útiles:

1. Transitividad: Si $f \in O(g)$ y $g \in O(h)$, entonces $f \in O(h)$

2. Reflexividad: $f \in \Theta(f)$

3. Simetría: Si $f \in \Theta(g)$, entonces $g \in \Theta(f)$

4. Suma: $O(f) + O(g) = O(\max(f, g))$

5. Producto: $O(f) \cdot O(g) = O(f \cdot g)$

Ejercicios de Notaciones Asintóticas¶

Jerarquía de Complejidades¶

Clasificación Detallada¶

Constante: $O(1)$¶

Características:

• El tiempo no depende del tamaño de entrada

• Más eficiente posible

• Ejemplo: acceso a un elemento de arreglo, operaciones aritméticas

Código ejemplo:

1
2
3
int obtener_primero(int arr[], int n) {
    return arr[0];  // O(1): una operación, independiente de n
}

Logarítmica: $O(\log n)$¶

Características:

• Crece muy lentamente

• Típica de algoritmos que dividen el problema a la mitad en cada paso

• Base del logaritmo irrelevante asintóticamente: la base del logaritmo no afecta a la clase de complejidad porque cambiar de base equivale a multiplicar por una constante. Si aplicamos la fórmula de cambio de base:

  $$\log_a n = \frac{\log_b n}{\log_b a} = \left(\frac{1}{\log_b a}\right) \log_b n$$

  (3)

  Dado que $\frac{1}{\log_b a}$ es una constante para bases fijas $a$ y $b$, por definición asintótica se cumple que $\log_a n \in \Theta(\log_b n)$ (por ejemplo, $\log_2 n \in \Theta(\log_{10} n)$).

Ejemplos: búsqueda binaria, operaciones en árboles balanceados

Código ejemplo:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Búsqueda binaria: O(log n)
// Precondición: el arreglo 'arr' debe estar ordenado de menor a mayor.
int busqueda_binaria(int arr[], int n, int clave) {
    int izq = 0, der = n - 1;
    
    while (izq <= der) {  // Se reduce a la mitad en cada lazo
        int medio = izq + (der - izq) / 2;
        
        if (arr[medio] == clave) {
            return medio;
        }
        
        if (arr[medio] < clave) {
            izq = medio + 1;
        } else {
            der = medio - 1;
        }
    }
    
    return -1;
}

Análisis:

En cada iteración del lazo, el espacio de búsqueda se reduce a la mitad. Si inicialmente hay $n$ elementos, después de $k$ lazos quedan $\frac{n}{2^k}$. El algoritmo termina cuando $\frac{n}{2^k} = 1$, es decir, $k = \log_2 n$.

Lineal: $O(n)$¶

Características:

• Tiempo proporcional al tamaño de entrada

• Óptimo para problemas que requieren examinar todos los datos

• Duplicar la entrada duplica el tiempo

Ejemplos: búsqueda secuencial, recorrer un arreglo, suma de elementos

Código ejemplo:

1
2
3
4
5
6
7
8
9
10
// Suma de elementos: O(n)
int sumar_elementos(int arr[], int n) {
    int suma = 0;
    
    for (int i = 0; i < n; i++) {  // n iteraciones
        suma += arr[i];  // O(1) por iteración
    }
    
    return suma;
}

Log-Lineal: $O(n \log n)$¶

Características:

• Complejidad de algoritmos óptimos de ordenamiento por comparación

• Crece más que lineal pero menos que cuadrático

• Muy eficiente en la práctica

Ejemplos: Merge Sort, Heap Sort, Quick Sort (promedio)

Código ejemplo (Merge Sort):

1
2
3
4
5
6
7
8
9
10
// Merge Sort: O(n log n)
void merge_sort(int arr[], int izq, int der) {
    if (izq < der) {
        int medio = izq + (der - izq) / 2;
        
        merge_sort(arr, izq, medio);      // T(n/2)
        merge_sort(arr, medio + 1, der);  // T(n/2)
        merge(arr, izq, medio, der);      // O(n)
    }
}

Análisis: La recurrencia es $T(n) = 2T(n/2) + O(n)$, que resuelve a $T(n) = O(n \log n)$ por el Teorema Maestro.

Cuadrática: $O(n^2)$¶

Características:

• Típica de algoritmos con dos lazos anidados

• Duplicar la entrada cuadruplica el tiempo

• Práctica para $n$ pequeño, inviable para $n$ grande

Ejemplos: Bubble Sort, Selection Sort, Insertion Sort

Código ejemplo:

1
2
3
4
5
6
7
8
9
10
// Bubble Sort: O(n²)
void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {           // n iteraciones
        for (int j = 0; j < n - i - 1; j++) {   // n-i iteraciones
            if (arr[j] > arr[j + 1]) {
                intercambiar(&arr[j], &arr[j + 1]);  // O(1)
            }
        }
    }
}

Análisis: Total de comparaciones = $\sum_{i=0}^{n-1} (n-i) = \frac{n(n-1)}{2} \in \Theta(n^2)$

Cúbica: $O(n^3)$¶

Características:

• Tres lazos anidados o algoritmos con subcubos

• Viable solo para $n$ pequeño

Ejemplos: multiplicación ingenua de matrices, algunos algoritmos de grafos

Código ejemplo:

1
2
3
4
5
6
7
8
9
10
11
// Multiplicación de matrices: O(n³)
void multiplicar_matrices(int A[][N], int B[][N], int C[][N], int n) {
    for (int i = 0; i < n; i++) {         // n iteraciones
        for (int j = 0; j < n; j++) {     // n iteraciones
            C[i][j] = 0;
            for (int k = 0; k < n; k++) { // n iteraciones
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
}

Exponencial: $O(2^n)$¶

Características:

• Crece extremadamente rápido

• Inviable para $n > 30$ en la mayoría de casos

• Común en algoritmos de fuerza bruta

Ejemplos: subconjuntos de un conjunto, Torre de Hanoi, algunos problemas NP-completos

Código ejemplo:

1
2
3
4
5
6
7
// Fibonacci recursivo ingenuo: O(2^n)
int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);  // Dos llamadas recursivas
}

Análisis: La relación de recurrencia para el tiempo de ejecución es $T(n) = T(n-1) + T(n-2) + O(1)$. Para resolver la parte homogénea de esta ecuación de diferencias, $T(n) - T(n-1) - T(n-2) = 0$, proponemos una solución de la forma $T(n) = r^n$. Al sustituir, obtenemos la ecuación característica:

cuyas raíces son $r_1 = \frac{1+\sqrt{5}}{2} = \phi \approx 1.618$ (la razón áurea) y $r_2 = \frac{1-\sqrt{5}}{2} \approx -0.618$. La solución general de la recurrencia es una combinación lineal de ambas potencias, dominada asintóticamente por la raíz de mayor magnitud, por lo que $T(n) \in \Theta(\phi^n)$.

Factorial: $O(n!)$¶

Características:

• La complejidad más ineficiente de las comunes

• Solo viable para $n < 15$ aproximadamente

• Aparece en problemas de permutaciones

Ejemplos: generar todas las permutaciones, problema del viajante (fuerza bruta)

Código ejemplo:

1
2
3
4
5
6
7
8
9
10
11
12
13
// Generar permutaciones: O(n!)
void generar_permutaciones(int arr[], int inicio, int fin) {
    if (inicio == fin) {
        imprimir(arr, fin + 1);
        return;
    }
    
    for (int i = inicio; i <= fin; i++) {
        intercambiar(&arr[inicio], &arr[i]);
        generar_permutaciones(arr, inicio + 1, fin);  // (n-1)! llamadas
        intercambiar(&arr[inicio], &arr[i]);
    }
}

Tabla Comparativa de Crecimiento¶

Ejercicios de Jerarquía de Complejidades¶

Técnicas de Análisis¶

Análisis de Lazos¶

Lazo Simple¶

1
2
3
for (int i = 0; i < n; i++) {
    // Operación O(1)
}

Análisis: $\sum_{i=0}^{n-1} O(1) = O(n)$

Lazos Anidados¶

1
2
3
4
5
for (int i = 0; i < n; i++) {       // n iteraciones
    for (int j = 0; j < n; j++) {   // n iteraciones
        // Operación O(1)
    }
}

Análisis: $\sum_{i=0}^{n-1} \sum_{j=0}^{n-1} O(1) = n \cdot n \cdot O(1) = O(n^2)$

Lazos con Dependencia¶

1
2
3
4
5
for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {  // Depende de i
        // Operación O(1)
    }
}

Análisis:

Lazo Logarítmico¶

1
2
3
for (int i = 1; i < n; i *= 2) {
    // Operación O(1)
}

Análisis: Si $i$ comienza en 1 y se duplica cada iteración, el lazo ejecuta $k$ veces donde $2^k = n$, es decir, $k = \log_2 n$. Por tanto, $O(\log n)$.

Análisis de Recursión¶

Método de Sustitución¶

El método de sustitución (o método de inducción matemática) se utiliza para resolver recurrencias mediante dos etapas:

1. Expandir (desarrollar) la relación de recurrencia para adivinar el patrón de la solución.

2. Probar la solución por inducción matemática para verificar su exactitud formal.

Ejemplo de desarrollo paso a paso: Consideremos la recurrencia $T(n) = T(n-1) + c$, donde $c$ es el costo constante de la operación básica ($O(1)$), con el caso base $T(1) = d$ (donde $d$ es otra constante).

1. Expansión por sustitución sucesiva: Comenzamos sustituyendo recursivamente la fórmula:

   • Paso 1: $T(n) = T(n-1) + c$

   • Paso 2: Sustituimos $T(n-1)$ usando la misma definición: $T(n-1) = T(n-2) + c$.

     $$T(n) = (T(n-2) + c) + c = T(n-2) + 2c$$

     (6)

   • Paso 3: Sustituimos $T(n-2) = T(n-3) + c$:

     $$T(n) = (T(n-3) + c) + 2c = T(n-3) + 3c$$

     (7)

2. Generalización del patrón: Podemos generalizar la expresión para el paso $k$:

   $$T(n) = T(n-k) + k \cdot c$$

   (8)

3. Aplicación del caso base: Deseamos alcanzar el caso base $T(1)$. Para ello, definimos $n - k = 1$, lo que implica $k = n - 1$. Sustituyendo $k$ en nuestra ecuación generalizada:

   $$T(n) = T(1) + (n-1) \cdot c$$

   (9)
   $$T(n) = d + c \cdot n - c$$

   (10)
   $$T(n) = c \cdot n + (d - c)$$

   (11)

Dado que $c$ y $d$ son constantes, la función de costo se reduce a una ecuación lineal:

Método del Árbol de Recursión¶

Antes de enunciar el Teorema Maestro, es fundamental visualizar cómo se distribuye el trabajo en un algoritmo recursivo de tipo divide y vencerás. El árbol de recursión es una herramienta gráfica donde:

• Cada nodo representa una llamada recursiva.

• El costo etiquetado en cada nodo es el trabajo no recursivo realizado en esa llamada específica.

• La suma del trabajo de todos los nodos en todos los niveles del árbol determina el costo total del algoritmo.

Ejemplo de análisis con árbol: Consideremos la recurrencia $T(n) = 2T(n/2) + n$ (con caso base $T(1) = O(1)$):

Nivel 0:                n              → costo: n
                       / \
Nivel 1:            n/2   n/2          → costo: n
                     / \   / \
Nivel 2:         n/4 n/4 n/4 n/4       → costo: n
                  ...

• Cantidad de subproblemas por nivel: En el nivel $j$, tenemos $2^j$ subproblemas.

• Tamaño de cada subproblema: En el nivel $j$, cada subproblema tiene tamaño $n/2^j$.

• Costo del trabajo no recursivo por nivel: En cada nivel $j$, la suma del trabajo es $2^j \times (n/2^j) = n$.

• Altura del árbol (número de niveles): Dado que el tamaño del problema se divide por 2 en cada paso, el proceso finaliza cuando $n/2^j = 1$, es decir, tras $j = \log_2 n$ niveles.

• Costo total: Sumando todos los niveles, el costo total es $n \times \log_2 n$, lo que equivale a $\Theta(n \log n)$.

Teorema Maestro¶

El Teorema Maestro es una receta matemática que sistematiza este análisis para recurrencias de la forma general:

donde:

• $a \geq 1$ es la cantidad de subproblemas recursivos creados.

• $b > 1$ es el factor por el cual se divide el tamaño del problema original.

• $f(n)$ es una función asintóticamente positiva que representa el costo de la división y combinación del trabajo en el nivel actual.

Al comparar el trabajo en las hojas del árbol (que es $\Theta(n^{\log_b a})$) con el trabajo no recursivo en la raíz ($f(n)$), el Teorema Maestro determina cuál de los dos domina la complejidad asintótica:

Caso 1 (Dominan las hojas): Si $f(n) \in O(n^{\log_b a - \epsilon})$ para algún $\epsilon > 0$, entonces:

Caso 2 (Trabajo balanceado): Si $f(n) \in \Theta(n^{\log_b a} \log^k n)$ para algún $k \geq 0$, entonces:

Caso 3 (Domina la raíz): Si $f(n) \in \Omega(n^{\log_b a + \epsilon})$ para algún $\epsilon > 0$, y se cumple la condición de regularidad ($a f(n/b) \leq c f(n)$ para alguna constante $c < 1$ y $n$ suficientemente grande), entonces:

La condición de regularidad garantiza que la tasa de trabajo no recursivo decrezca geométricamente a medida que se desciende en el árbol de recursión. Si no se satisface esta condición, no se puede aplicar el Caso 3 del Teorema Maestro.

Ejemplos de aplicación:

1. Merge Sort: $T(n) = 2T(n/2) + O(n)$

   • $a=2, b=2, f(n)=n$

   • $\log_b a = \log_2 2 = 1$

   • $f(n) = n \in \Theta(n^1)$ → Caso 2 con $k=0$

   • Solución: $T(n) \in \Theta(n \log n)$

2. Búsqueda Binaria: $T(n) = T(n/2) + O(1)$

   • $a=1, b=2, f(n)=1$

   • $\log_b a = 0$

   • $f(n) = 1 \in \Theta(n^0)$ → Caso 2 con $k=0$

   • Solución: $T(n) \in \Theta(\log n)$

3. Multiplicación de Karatsuba: $T(n) = 3T(n/2) + O(n)$

   • $a=3, b=2, f(n)=n$

   • $\log_b a = \log_2 3 \approx 1.585$

   • $f(n) = n \in O(n^{1.585-\epsilon})$ → Caso 1

   • Solución: $T(n) \in \Theta(n^{\log_2 3}) \approx \Theta(n^{1.585})$

Análisis Amortizado¶

El análisis amortizado considera el costo promedio de una secuencia de operaciones, permitiendo que algunas operaciones sean costosas si la mayoría son baratas.

Método del Agregado¶

Ejemplo: Arreglo dinámico redimensionable en C.

Supongamos que implementamos un arreglo dinámico en C mediante una estructura que almacena un puntero, el tamaño actual y la capacidad máxima de almacenamiento. Cuando el arreglo alcanza su capacidad límite, duplicamos su tamaño utilizando realloc:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef struct {
    int *datos;
    size_t tamaño;
    size_t capacidad;
} arreglo_dinamico_t;

bool insertar_arreglo(arreglo_dinamico_t *arr, int valor) {
    if (arr->tamaño >= arr->capacidad) {
        size_t nueva_capacidad = arr->capacidad * 2;
        int *nuevo_espacio = realloc(arr->datos, nueva_capacidad * sizeof(int));
        if (nuevo_espacio == NULL) {
            return false;
        }
        arr->datos = nuevo_espacio;
        arr->capacidad = nueva_capacidad;
    }
    arr->datos[arr->tamaño] = valor;
    arr->tamaño++;
    return true;
}

Analicemos el costo de una secuencia de $n$ inserciones consecutivas en el lazo de carga, comenzando con una capacidad inicial de 1:

• Si la inserción no requiere redimensionamiento, toma tiempo constante: 1 operación.

• Si requiere redimensionamiento, requiere reasignar memoria y copiar los elementos existentes, tomando $i$ operaciones (donde $i$ es el tamaño en ese momento).

Para $n$ inserciones (donde $n$ es una potencia de 2), el costo total acumulado es la suma de los accesos normales y los costos de copia por redimensionamiento:

Costo amortizado: Al dividir el costo total por la cantidad de operaciones, obtenemos $\frac{3n}{n} = O(1)$ por cada inserción individual.

Método del Potencial¶

El método del potencial analiza la complejidad amortizada definiendo una función potencial $\Phi$ sobre los estados de la estructura de datos. Esta función asocia un número real no negativo $\Phi(D_i)$ a la estructura tras la operación $i$.

El costo amortizado $\hat{c}_i$ de la $i$-ésima operación se define como:

donde $c_i$ es el costo real de la operación y $\Delta\Phi_i = \Phi(D_i) - \Phi(D_{i-1})$ es el cambio en el potencial.

Análisis del Arreglo Dinámico Para un arreglo dinámico, definimos la función potencial después de la operación $i$ como:

donde $t_i$ es el tamaño actual (número de elementos) y $c_i$ es la capacidad actual.

Precondición de validez: Como la capacidad es a lo sumo el doble del tamaño y al menos igual, tenemos que $\Phi_i \ge 0$. Inicialmente, con un arreglo vacío, $t_0 = 0$ y $c_0 = 0$, por lo que $\Phi_0 = 0$.

Analicemos los dos escenarios posibles para la $i$-ésima inserción:

Escenario 1: Inserción sin Redimensionamiento

El arreglo tiene espacio libre ($t_{i-1} < c_{i-1}$).

1. El costo real es constante: $c_i = 1$ (copiar el elemento en el arreglo).

2. El tamaño aumenta en uno ($t_i = t_{i-1} + 1$), y la capacidad permanece constante ($c_i = c_{i-1}$).

3. El cambio en el potencial es:

   $$\Delta\Phi_i = \Phi_i - \Phi_{i-1} = (2 \cdot t_i - c_i) - (2 \cdot t_{i-1} - c_{i-1})$$

   (20)
   $$\Delta\Phi_i = (2(t_{i-1} + 1) - c_{i-1}) - (2 \cdot t_{i-1} - c_{i-1}) = 2$$

   (21)

4. El costo amortizado calculado es:

   $$\hat{c}_i = c_i + \Delta\Phi_i = 1 + 2 = 3$$

   (22)

Escenario 2: Inserción con Redimensionamiento

El arreglo está lleno ($t_{i-1} = c_{i-1}$). Para insertar, se debe duplicar la capacidad: $c_i = 2 \cdot c_{i-1}$.

1. El costo real de esta inserción implica alocar nueva memoria y copiar todos los elementos existentes más el nuevo: $c_i = t_{i-1} + 1$.

2. El tamaño aumenta en uno ($t_i = t_{i-1} + 1$), y la capacidad se duplica ($c_i = 2 \cdot t_{i-1}$).

3. Calculamos la variación del potencial $\Delta\Phi_i$:

   $$\Phi_{i-1} = 2 \cdot t_{i-1} - c_{i-1} = 2 \cdot t_{i-1} - t_{i-1} = t_{i-1}$$

   (23)
   $$\Phi_i = 2 \cdot t_i - c_i = 2(t_{i-1} + 1) - 2 \cdot t_{i-1} = 2$$

   (24)
   $$\Delta\Phi_i = \Phi_i - \Phi_{i-1} = 2 - t_{i-1}$$

   (25)

4. El costo amortizado calculado es:

   $$\hat{c}_i = c_i + \Delta\Phi_i = (t_{i-1} + 1) + (2 - t_{i-1}) = 3$$

   (26)

Conclusión En ambos escenarios (con o sin redimensionamiento), el costo amortizado de una inserción en el arreglo dinámico es exactamente 3, lo que demuestra formalmente que la operación de inserción tiene una complejidad de amortización constante:

Ejercicios de Técnicas de Análisis¶

Complejidad Espacial¶

La complejidad espacial mide la cantidad de memoria adicional que un algoritmo requiere.

Clasificación¶

• $O(1)$: Espacio constante, independiente de la entrada

• $O(\log n)$: Típico de algoritmos recursivos que dividen el problema

• $O(n)$: Espacio lineal, como copiar un arreglo

• $O(n^2)$: Matrices cuadradas

Recursión y Pila de Llamadas¶

Cada llamada recursiva ocupa espacio en la pila. La profundidad máxima de recursión determina la complejidad espacial.

Ejemplo: Fibonacci recursivo

1
2
3
4
5
6
int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

• Complejidad temporal: $O(2^n)$

• Complejidad espacial: $O(n)$ (profundidad máxima de la pila)

Trade-off Tiempo-Espacio¶

A menudo es posible reducir tiempo usando más espacio (memoización) o viceversa.

Ejemplo: Fibonacci con memoización

1
2
3
4
5
6
7
8
9
10
11
int fibonacci_memo(int n, int memo[]) {
    if (n <= 1) {
        return n;
    }
    if (memo[n] != -1) {
        return memo[n];
    }
    
    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo);
    return memo[n];
}

• Complejidad temporal: $O(n)$ (cada valor se calcula una vez)

• Complejidad espacial: $O(n)$ (arreglo de memoización + pila)

Ejercicios de Complejidad Espacial¶

Límites Inferiores y Óptimalidad¶

Límites Inferiores Basados en Información¶

Un límite inferior establece que ningún algoritmo puede resolver un problema más rápido que cierta complejidad.

Teorema: Ordenamiento por Comparación¶

Enunciado: Cualquier algoritmo que ordene $n$ elementos mediante comparaciones requiere al menos $\Omega(n \log n)$ comparaciones en el peor caso.

Demostración (árbol de decisión):

1. Un algoritmo de ordenamiento por comparación puede modelarse como un árbol binario de decisión.

2. Cada hoja representa una permutación posible de los $n$ elementos de entrada.

3. Hay $n!$ permutaciones posibles, por tanto, el árbol debe tener al menos $n!$ hojas.

4. Un árbol binario de altura $h$ tiene como máximo $2^h$ hojas.

5. Para que el árbol pueda representar todas las salidas válidas, se requiere que $2^h \geq n!$, lo que implica $h \geq \log_2(n!)$.

6. Demostramos la cota inferior de $\log_2(n!)$ expandiendo la sumatoria y acotándola inferiormente desde su término medio: $$ \log_2(n!) = \sum_{i=1}^n \log_2 i \geq \sum_{i=n/2}^n \log_2 i \geq \sum_{i=n/2}^n \log_2(n/2) = \frac{n}{2} \log_2(n/2) = \frac{n}{2} (\log_2 n

   • 1. \in \Omega(n \log n) $$

Conclusión: Cualquier algoritmo basado en comparaciones requiere al menos $\Omega(n \log n)$ comparaciones en el peor caso. Algoritmos como Merge Sort y Heap Sort son, por lo tanto, óptimos.

Algoritmos Óptimos¶

Un algoritmo es asintóticamente óptimo si su complejidad coincide con el límite inferior teórico del problema.

Ejemplos:

• Búsqueda en arreglo no ordenado: $\Theta(n)$ (deben revisarse todos los elementos)

• Multiplicación de matrices: $O(n^{2.376})$ (algoritmo de Coppersmith-Winograd), límite inferior $\Omega(n^2)$

Más Allá: Una Introducción a la Teoría de la Complejidad (P vs. NP)¶

Mientras que el análisis de algoritmos se enfoca en determinar la eficiencia de una solución específica, la teoría de la complejidad aborda una pregunta más fundamental: ¿cuál es la dificultad inherente de un problema? No se pregunta “¿cuán rápido es mi algoritmo para ordenar?”, sino “¿cuán rápido puede ser cualquier algoritmo que ordene?”.

Esta disciplina clasifica los problemas computacionales en clases de complejidad basadas en los recursos (tiempo y memoria) que se requieren para resolverlos en el peor de los casos, independientemente del algoritmo específico utilizado.

Conceptos de Complejidad: Intratabilidad y las Clases P y NP¶

En el análisis de algoritmos, no solo nos interesa determinar la complejidad asintótica exacta, sino también clasificar los problemas según si son resolubles de forma eficiente en la práctica. Esta distinción introduce la noción de intratabilidad.

Problemas Tratables vs. Intratables¶

• Problemas Tratables: Son aquellos para los cuales existe un algoritmo que los resuelve en tiempo polinomial en el peor de los casos (es decir, $O(n^k)$ para alguna constante $k$). Cuando la entrada crece, el tiempo requerido aumenta de forma manejable por el hardware. Ejemplos: Ordenar una lista, buscar un elemento en un arreglo, encontrar el camino más corto en un grafo.

• Problemas Intratables: Son problemas de gran complejidad computacional para los cuales no se conocen algoritmos polinomiales que garanticen una solución óptima en el peor de los casos. Sus mejores algoritmos conocidos requieren tiempo exponencial (ej. $O(2^n)$) o factorial (ej. $O(n!)$), volviéndolos imposibles de computar para tamaños de entrada moderados.

Las Clases P y NP¶

Para formalizar esta clasificación, la teoría de la complejidad define conjuntos de problemas llamados clases de complejidad:

• La Clase P: Contiene a todos los problemas de decisión (cuya respuesta es “sí” o “no”) que pueden ser resueltos eficientemente en tiempo polinomial.

• La Clase NP (Tiempo Polinomial No Determinista): Contiene a los problemas de decisión para los cuales, si bien encontrar una solución puede ser computacionalmente difícil, es posible verificar la validez de una solución propuesta (un certificado) en tiempo polinomial. Ejemplo (Satisfacibilidad Booleana - SAT): Evaluar si existe una asignación de variables lógicas que haga verdadera una fórmula booleana. Encontrar la combinación exacta puede requerir probar exponencialmente muchas opciones ($2^n$), pero verificar si una asignación dada satisface la fórmula toma tiempo lineal en el tamaño de la fórmula. Por lo tanto, SAT pertenece a la clase NP.

La Cuestión $P \neq NP$ y los Problemas NP-Completos¶

La relación entre estas clases plantea uno de los interrogantes abiertos más importantes de la ciencia de la computación: ¿Es $P = NP$? Es decir: si la solución a un problema se puede verificar eficientemente, ¿se puede también encontrar de forma eficiente?

El consenso científico generalizado es que $P \neq NP$, lo que significa que verificar soluciones es fundamentalmente más sencillo que crearlas.

Dentro de la clase NP, existen problemas denominados NP-Completos. Estos problemas representan los elementos más difíciles de NP. Tienen la propiedad de que si se encontrara un algoritmo eficiente (polinomial) para resolver cualquiera de ellos, ese algoritmo podría adaptarse inmediatamente para resolver todos los problemas de la clase NP en tiempo polinomial, demostrando que $P = NP$.

Ejemplos clásicos:

• El problema del Viajante (TSP) en su versión de decisión.

• Coloreado de grafos.

Visualización de las Clases de Complejidad¶

Asumiendo que P ≠ NP, la relación entre estas clases se puede visualizar de la siguiente manera:

Frente a la intratabilidad de los problemas NP-Completos, en el desarrollo práctico de software se emplean algoritmos de aproximación, heurísticas o restricciones del dominio para hallar soluciones aceptables en tiempos razonables, sabiendo que una solución óptima general y rápida no es viable.

Ejemplos Detallados de Análisis¶

Ejemplo 1: Búsqueda del Máximo¶

1
2
3
4
5
6
7
8
9
10
11
int buscar_maximo(int arr[], int n) {
    int max = arr[0];          // O(1)
    
    for (int i = 1; i < n; i++) {  // n-1 iteraciones
        if (arr[i] > max) {    // O(1)
            max = arr[i];      // O(1)
        }
    }
    
    return max;  // O(1)
}

Análisis:

• Inicialización: $O(1)$

• Lazo: $(n-1) \times O(1) = O(n)$

• Complejidad total: $T(n) = O(1) + O(n) + O(1) = O(n)$

• Optimalidad: Es óptimo porque debemos examinar todos los elementos al menos una vez para garantizar que encontramos el máximo

Ejemplo 2: Búsqueda de Duplicados¶

1
2
3
4
5
6
7
8
9
10
11
// Versión ingenua: O(n²)
bool tiene_duplicados_ingenuo(int arr[], int n) {
    for (int i = 0; i < n; i++) {           // n iteraciones
        for (int j = i + 1; j < n; j++) {   // (n-i-1) iteraciones
            if (arr[i] == arr[j]) {
                return true;  // O(1)
            }
        }
    }
    return false;
}

Análisis:

1
2
3
4
5
6
7
8
9
10
11
12
// Versión optimizada: O(n log n) con ordenamiento previo
bool tiene_duplicados_ordenado(int arr[], int n) {
    qsort(arr, n, sizeof(int), comparar);  // O(n log n)
    
    for (int i = 0; i < n - 1; i++) {      // O(n)
        if (arr[i] == arr[i + 1]) {
            return true;
        }
    }
    
    return false;
}

Análisis: $T(n) = O(n \log n) + O(n) = O(n \log n)$

Ejemplo 3: Torres de Hanoi¶

1
2
3
4
5
6
7
8
9
10
void hanoi(int n, char origen, char destino, char auxiliar) {
    if (n == 1) {
        printf("Mover disco 1 de %c a %c\n", origen, destino);
        return;
    }
    
    hanoi(n - 1, origen, auxiliar, destino);
    printf("Mover disco %d de %c a %c\n", n, origen, destino);
    hanoi(n - 1, auxiliar, destino, origen);
}

Análisis mediante recurrencia: $$

$$

Solución por sustitución: $$

$$

Cuando $k = n-1$:

Conclusión: Torres de Hanoi es inherentemente exponencial. No existe solución más eficiente.

Ejercicios de Autoevaluación¶