Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

Análisis de Complejidad Algorítmica

Fundamentos matemáticos del análisis asintótico

Universidad Nacional de Rio Negro - Sede Andina

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 (nn) 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)=3n2+100n+500T(n) = 3n^2 + 100n + 500, observamos que para valores grandes de nn, el término 3n23n^2 domina a los demás. El análisis asintótico nos permite simplificar esta expresión a su orden de crecimiento, que es n2n^2, ignorando constantes multiplicativas (3) y términos de menor orden (100n+500100n + 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.

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.

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.

Notaciones Menos Comunes

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

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

0≤f(n)<c⋅g(n)∀n≥n00 \leq f(n) < c \cdot g(n) \quad \forall n \geq n_0
(1)

Equivalentemente: lim⁡n→∞f(n)g(n)=0\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0

Ejemplo: n∈o(n2)n \in o(n^2) pero n∉o(n)n \notin o(n)

Little-omega (Límite Inferior Estricto)

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

0≤c⋅g(n)<f(n)∀n≥n00 \leq c \cdot g(n) < f(n) \quad \forall n \geq n_0
(2)

Propiedades Algebraicas

Las notaciones asintóticas tienen propiedades útiles:

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

  2. Reflexividad: f∈Θ(f)f \in \Theta(f)

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

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

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

Jerarquía de Complejidades

Jerarquía de las clases de complejidad más comunes, ordenadas de más eficiente a menos eficiente.

Figure 1:Jerarquía de las clases de complejidad más comunes, ordenadas de más eficiente a menos eficiente.

Clasificación Detallada

Constante: O(1)O(1)

Características:

Código ejemplo:

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

Logarítmica: O(log⁡n)O(\log n)

Características:

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

Código ejemplo:

// Búsqueda binaria: O(log n)
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 iteración
        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, el espacio de búsqueda se reduce a la mitad. Si inicialmente hay nn elementos, después de kk iteraciones quedan n2k\frac{n}{2^k}. El algoritmo termina cuando n2k=1\frac{n}{2^k} = 1, es decir, k=log⁡2nk = \log_2 n.

Lineal: O(n)O(n)

Características:

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

Código ejemplo:

// 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(nlog⁡n)O(n \log n)

Características:

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

Código ejemplo (Merge Sort):

// 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)T(n) = 2T(n/2) + O(n), que resuelve a T(n)=O(nlog⁡n)T(n) = O(n \log n) por el Teorema Maestro.

Cuadrática: O(n2)O(n^2)

Características:

Ejemplos: Bubble Sort, Selection Sort, Insertion Sort

Código ejemplo:

// 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 = ∑i=0n−1(n−i)=n(n−1)2∈Θ(n2)\sum_{i=0}^{n-1} (n-i) = \frac{n(n-1)}{2} \in \Theta(n^2)

Cúbica: O(n3)O(n^3)

Características:

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

Código ejemplo:

// 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(2n)O(2^n)

Características:

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

Código ejemplo:

// 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 recurrencia T(n)=T(n−1)+T(n−2)+O(1)T(n) = T(n-1) + T(n-2) + O(1) tiene solución T(n)∈Θ(ϕn)T(n) \in \Theta(\phi^n) donde ϕ=1+52≈1.618\phi = \frac{1+\sqrt{5}}{2} \approx 1.618 (razón áurea).

Factorial: O(n!)O(n!)

Características:

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

Código ejemplo:

// 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]);
    }
}
Comparación del crecimiento de diferentes funciones de complejidad para valores de n hasta 100.

Figure 2:Comparación del crecimiento de diferentes funciones de complejidad para valores de nn hasta 100.

Tabla Comparativa de Crecimiento

nnlog⁡n\log nnnnlog⁡nn \log nn2n^2n3n^32n2^nn!n!
10310331001K1K3.6M
20420864008K1M2.4×10182.4 \times 10^{18}
3053014790027K1B2.7×10322.7 \times 10^{32}
100710066410K1M1.3×10301.3 \times 10^{30}9.3×101579.3 \times 10^{157}
1000101K9.9K1M1B——

Técnicas de Análisis

Análisis de Lazos

Lazo Simple

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

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

Lazos Anidados

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

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

Lazos con Dependencia

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

Análisis:

∑i=0n−1∑j=in−1O(1)=∑i=0n−1(n−i)=∑k=1nk=n(n+1)2∈O(n2)\sum_{i=0}^{n-1} \sum_{j=i}^{n-1} O(1) = \sum_{i=0}^{n-1} (n-i) = \sum_{k=1}^{n} k = \frac{n(n+1)}{2} \in O(n^2)
(3)

Lazo Logarítmico

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

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

Análisis de Recursión

Método de Sustitución

Ejemplo: T(n)=T(n−1)+O(1)T(n) = T(n-1) + O(1) con T(1)=O(1)T(1) = O(1)

Solución: $$

T(n)=T(n−1)+c=T(n−2)+c+c=T(n−2)+2c=T(n−3)+3c⋮=T(1)+(n−1)c=O(1)+O(n)=O(n)\begin{align} T(n) &= T(n-1) + c \\ &= T(n-2) + c + c = T(n-2) + 2c \\ &= T(n-3) + 3c \\ &\vdots \\ &= T(1) + (n-1)c \\ &= O(1) + O(n) = O(n) \end{align}
(4)

$$

Teorema Maestro

Para recurrencias de la forma:

T(n)=aT(nb)+f(n)T(n) = aT\left(\frac{n}{b}\right) + f(n)
(5)

donde a≥1a \geq 1, b>1b > 1 y f(n)f(n) es asintóticamente positiva, el Teorema Maestro proporciona la solución:

Caso 1: Si f(n)∈O(nlog⁡ba−ϵ)f(n) \in O(n^{\log_b a - \epsilon}) para algún ϵ>0\epsilon > 0, entonces:

T(n)∈Θ(nlog⁡ba)T(n) \in \Theta(n^{\log_b a})
(6)

Caso 2: Si f(n)∈Θ(nlog⁡balog⁡kn)f(n) \in \Theta(n^{\log_b a} \log^k n) para algún k≥0k \geq 0, entonces:

T(n)∈Θ(nlog⁡balog⁡k+1n)T(n) \in \Theta(n^{\log_b a} \log^{k+1} n)
(7)

Caso 3: Si f(n)∈Ω(nlog⁡ba+ϵ)f(n) \in \Omega(n^{\log_b a + \epsilon}) para algún ϵ>0\epsilon > 0, y af(n/b)≤cf(n)af(n/b) \leq cf(n) para algún c<1c < 1 y nn suficientemente grande, entonces:

T(n)∈Θ(f(n))T(n) \in \Theta(f(n))
(8)
Árbol de recursión ilustrando el Teorema Maestro y cómo se distribuye el trabajo en cada nivel.

Figure 3:Árbol de recursión ilustrando el Teorema Maestro y cómo se distribuye el trabajo en cada nivel.

Ejemplos de aplicación:

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

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

    • log⁡ba=log⁡22=1\log_b a = \log_2 2 = 1

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

    • Solución: T(n)∈Θ(nlog⁡n)T(n) \in \Theta(n \log n)

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

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

    • log⁡ba=0\log_b a = 0

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

    • Solución: T(n)∈Θ(log⁡n)T(n) \in \Theta(\log n)

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

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

    • log⁡ba=log⁡23≈1.585\log_b a = \log_2 3 \approx 1.585

    • f(n)=n∈O(n1.585−ϵ)f(n) = n \in O(n^{1.585-\epsilon}) → Caso 1

    • Solución: T(n)∈Θ(nlog⁡23)≈Θ(n1.585)T(n) \in \Theta(n^{\log_2 3}) \approx \Theta(n^{1.585})

Método del Árbol de Recursión

Visualiza la recursión como un árbol donde:

Ejemplo: T(n)=2T(n/2)+nT(n) = 2T(n/2) + n

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

Altura del árbol: log n
Costo por nivel: n
Costo total: n × log n = O(n log n)

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 (como std::vector de C++)

Operación push_back:

Si el arreglo duplica su tamaño cuando se llena, el costo de nn inserciones es:

∑i=0log⁡n2i=2log⁡n+1−1<2n\sum_{i=0}^{\log n} 2^i = 2^{\log n + 1} - 1 < 2n
(9)

Costo amortizado: 2nn=O(1)\frac{2n}{n} = O(1) por operación.

Método del Potencial

Define una función potencial Φ\Phi que representa “energía almacenada” en la estructura:

Costo amortizado=Costo real+ΔΦ\text{Costo amortizado} = \text{Costo real} + \Delta\Phi
(10)

Para arreglo dinámico: Φ=2×taman˜o−capacidad\Phi = 2 \times \text{tamaño} - \text{capacidad}

Complejidad Espacial

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

Clasificación

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

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

Trade-off Tiempo-Espacio

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

Ejemplo: Fibonacci con memoización

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];
}
Ilustración del trade-off entre tiempo y espacio en el problema de Fibonacci.

Figure 4:Ilustración del trade-off entre tiempo y espacio en el problema de Fibonacci.

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 nn elementos mediante comparaciones requiere al menos Ω(nlog⁡n)\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 nn elementos

  3. Hay n!n! permutaciones posibles, por tanto n!n! hojas

  4. Un árbol binario de altura hh tiene a lo más 2h2^h hojas

  5. Necesitamos 2h≥n!2^h \geq n!, es decir, h≥log⁡2(n!)h \geq \log_2(n!)

Por la aproximación de Stirling: log⁡2(n!)=Θ(nlog⁡n)\log_2(n!) = \Theta(n \log n)

Conclusión: Merge Sort, Heap Sort son óptimos para ordenamiento por comparación.

Algoritmos Óptimos

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

Ejemplos:

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.

Problemas de Decisión y el Modelo de Cómputo

Para formalizar el estudio, la teoría se centra en los problemas de decisión: aquellos que pueden ser respondidos con un simple “sí” o “no”. Aunque parece limitante, muchos problemas más complejos (como los de optimización) pueden reformularse como una serie de problemas de decisión.

El modelo formal de cómputo utilizado para definir estas clases es la Máquina de Turing, un autómata teórico que puede simular la lógica de cualquier algoritmo computacional.

La Clase P (Tiempo Polinomial)

La clase P contiene todos los problemas de decisión que pueden ser resueltos por una Máquina de Turing determinista en tiempo polinomial.

Ejemplos de problemas en P:

La Clase NP (Tiempo Polinomial No Determinista)

Aquí es donde surge una de las mayores confusiones en la informática. NP no significa “No Polinomial”. Significa Tiempo Polinomial No Determinista.

Existen dos definiciones equivalentes y muy importantes:

  1. Definición Formal: La clase NP es el conjunto de problemas de decisión que pueden ser resueltos por una Máquina de Turing no determinista en tiempo polinomial. (Una máquina no determinista puede explorar múltiples caminos de cómputo simultáneamente).

  2. Definición Práctica (y más útil): La clase NP es el conjunto de problemas de decisión para los cuales, si se nos proporciona una posible solución (un “certificado” o “testigo”), podemos verificar si es correcta en tiempo polinomial.

Ejemplo Clásico: El Problema de Satisfacibilidad Booleana (SAT)

Por lo tanto, SAT está en NP.

La Pregunta del Millón de Dólares: ¿P = NP?

Claramente, si un problema puede ser resuelto rápidamente (está en P), entonces su solución también puede ser verificada rápidamente. Esto significa que la clase P está contenida dentro de la clase NP.

La pregunta fundamental, uno de los siete Problemas del Milenio del Instituto Clay de Matemáticas, es: ¿Son estas dos clases realmente la misma? ¿Es P igual a NP?

Nadie ha sido capaz de probarlo en ninguna de las dos direcciones. Sin embargo, el consenso abrumador entre los científicos de la computación es que P ≠ NP.

Implicaciones de la Respuesta

Reducciones y la Noción de “El Problema más Difícil”

Para clasificar la dificultad relativa de los problemas dentro de NP, se utiliza el concepto de reducción en tiempo polinomial. Un problema A se “reduce” a un problema B si podemos transformar cualquier instancia de A en una instancia de B de tal manera que la solución para B nos da la solución para A, y esta transformación toma tiempo polinomial.

NP-Hard y NP-Completo

Los problemas NP-Completos son, en esencia, los problemas más difíciles de la clase NP.

El Teorema de Cook-Levin (1971) fue el hito que demostró que el problema SAT es NP-Completo. Desde entonces, se ha demostrado que miles de otros problemas importantes también lo son, mediante reducciones a partir de SAT u otros problemas NPC conocidos.

Ejemplos de Problemas NP-Completos:

La importancia de los problemas NPC es inmensa: si se encontrara un algoritmo de tiempo polinomial para un solo problema NP-Completo, automáticamente tendríamos un algoritmo eficiente para todos los problemas en NP, lo que probaría que P = NP.

Visualización de las Clases de Complejidad

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

Este diagrama ilustra que P y NPC son subconjuntos de NP. Los problemas NP-Hard pueden estar dentro o fuera de NP. El problema de la Factorización de Enteros, en el que se basa gran parte de la criptografía moderna, es un ejemplo fascinante: está en NP, pero no se sabe si es NP-Completo o si está en P.

Ejemplos Detallados de Análisis

Ejemplo 1: Búsqueda del Máximo

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:

Ejemplo 2: Búsqueda de Duplicados

// 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:

T(n)=∑i=0n−1∑j=i+1n−1O(1)=∑i=0n−1(n−i−1)=n(n−1)2∈O(n2)T(n) = \sum_{i=0}^{n-1} \sum_{j=i+1}^{n-1} O(1) = \sum_{i=0}^{n-1} (n-i-1) = \frac{n(n-1)}{2} \in O(n^2)
(11)
// 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(nlog⁡n)+O(n)=O(nlog⁡n)T(n) = O(n \log n) + O(n) = O(n \log n)

Ejemplo 3: Torres de Hanoi

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: $$

T(n)=2T(n−1)+O(1)T(1)=O(1)\begin{align} T(n) &= 2T(n-1) + O(1) \\ T(1) &= O(1) \end{align}
(12)

$$

Solución por sustitución: $$

T(n)=2T(n−1)+1=2(2T(n−2)+1)+1=4T(n−2)+2+1=8T(n−3)+4+2+1=2kT(n−k)+(2k−1+2k−2+⋯+2+1)=2kT(n−k)+(2k−1)\begin{align} T(n) &= 2T(n-1) + 1 \\ &= 2(2T(n-2) + 1) + 1 = 4T(n-2) + 2 + 1 \\ &= 8T(n-3) + 4 + 2 + 1 \\ &= 2^k T(n-k) + (2^{k-1} + 2^{k-2} + \cdots + 2 + 1) \\ &= 2^k T(n-k) + (2^k - 1) \end{align}
(13)

$$

Cuando k=n−1k = n-1:

T(n)=2n−1T(1)+2n−1−1=2n−1+2n−1−1=2n−1∈Θ(2n)T(n) = 2^{n-1}T(1) + 2^{n-1} - 1 = 2^{n-1} + 2^{n-1} - 1 = 2^n - 1 \in \Theta(2^n)
(14)

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

Ejercicios

Solution to Exercise 1

a) O(n2)O(n^2)

  • Lazo externo: nn iteraciones

  • Lazo interno: ii iteraciones (depende de ii)

  • Total: ∑i=0n−1i=n(n−1)2∈O(n2)\sum_{i=0}^{n-1} i = \frac{n(n-1)}{2} \in O(n^2)

b) O(nlog⁡n)O(n \log n)

  • Lazo externo: log⁡3n\log_3 n iteraciones (crece multiplicativamente)

  • Lazo interno: nn iteraciones

  • Total: n×log⁡3n∈O(nlog⁡n)n \times \log_3 n \in O(n \log n)

c) O(n)O(n)

  • Recurrencia: T(n)=2T(n/3)+O(n)T(n) = 2T(n/3) + O(n)

  • Por Teorema Maestro: a=2,b=3,f(n)=na=2, b=3, f(n)=n

  • log⁡ba=log⁡32≈0.631<1\log_b a = \log_3 2 \approx 0.631 < 1

  • Caso 3: T(n)∈Θ(n)T(n) \in \Theta(n)

Solution to Exercise 2

Debemos encontrar constantes c1,c2,n0c_1, c_2, n_0 tales que:

c1n2≤3n2+5n+2≤c2n2∀n≥n0c_1 n^2 \leq 3n^2 + 5n + 2 \leq c_2 n^2 \quad \forall n \geq n_0
(15)

Cota inferior (c1n2≤3n2+5n+2c_1 n^2 \leq 3n^2 + 5n + 2):

  • Tomemos c1=3c_1 = 3

  • Para n≥1n \geq 1: 3n2≤3n2+5n+23n^2 \leq 3n^2 + 5n + 2 ✓

Cota superior (3n2+5n+2≤c2n23n^2 + 5n + 2 \leq c_2 n^2):

  • Necesitamos c2c_2 tal que 3n2+5n+2≤c2n23n^2 + 5n + 2 \leq c_2 n^2

  • Para n≥1n \geq 1: 5n≤5n25n \leq 5n^2 y 2≤2n22 \leq 2n^2

  • Entonces: 3n2+5n+2≤3n2+5n2+2n2=10n23n^2 + 5n + 2 \leq 3n^2 + 5n^2 + 2n^2 = 10n^2

  • Tomemos c2=10c_2 = 10

Conclusión: Con c1=3c_1 = 3, c2=10c_2 = 10, n0=1n_0 = 1:

3n2≤3n2+5n+2≤10n2∀n≥13n^2 \leq 3n^2 + 5n + 2 \leq 10n^2 \quad \forall n \geq 1
(16)

Por tanto, f(n)∈Θ(n2)f(n) \in \Theta(n^2).

Solution to Exercise 3

Solución óptima: O(n)O(n)

void dos_maximos(int arr[], int n, int *max1, int *max2) {
    // Inicializar
    if (arr[0] > arr[1]) {
        *max1 = arr[0];
        *max2 = arr[1];
    } else {
        *max1 = arr[1];
        *max2 = arr[0];
    }
    
    // Un solo recorrido: O(n)
    for (int i = 2; i < n; i++) {
        if (arr[i] > *max1) {
            *max2 = *max1;
            *max1 = arr[i];
        } else if (arr[i] > *max2) {
            *max2 = arr[i];
        }
    }
}

Análisis:

  • Un único recorrido del arreglo: O(n)O(n)

  • Operaciones constantes por elemento

  • Complejidad: O(n)O(n)

Comparación con ordenamiento:

  • Ordenar todo el arreglo: O(nlog⁡n)O(n \log n)

  • Tomar los dos últimos elementos: O(1)O(1)

  • Complejidad total: O(nlog⁡n)O(n \log n)

Conclusión: La solución óptima es asintóticamente mejor (O(n)O(n) vs O(nlog⁡n)O(n \log n)).

Referencias y Lecturas Complementarias

Textos Fundamentales

Recursos Avanzados

Recursos en Línea

Resumen

El análisis de complejidad es fundamental para:

  1. Predecir rendimiento: Saber si un algoritmo será viable para el tamaño de entrada esperado

  2. Comparar algoritmos: Elegir el más eficiente para cada situación

  3. Identificar cuellos de botella: Localizar partes del código que necesitan optimización

  4. Establecer límites teóricos: Determinar si un algoritmo es óptimo o puede mejorarse

Puntos Clave

Guía Práctica de Decisión

Para elegir un algoritmo:

  1. ¿Cuál es el tamaño típico de entrada?

    • Pequeño (n<100n < 100): Casi cualquier complejidad funciona

    • Mediano (n∼104n \sim 10^4): Evitar O(n3)O(n^3) o peor

    • Grande (n>106n > 10^6): Necesario O(n)O(n) o O(nlog⁡n)O(n \log n)

  2. ¿Importa más tiempo o espacio?

    • Tiempo crítico: Considera usar más memoria (memoización, tablas hash)

    • Espacio limitado: Acepta algoritmos más lentos si usan menos memoria

  3. ¿Es un problema conocido?

    • Usa algoritmos estándar óptimos cuando existan

    • Para problemas NP-completos, considera aproximaciones o heurísticas

El análisis de complejidad no reemplaza la medición empírica, pero proporciona garantías teóricas esenciales para el diseño de software robusto y escalable.

Apunte
13 - TAD, Pilas y Colas
Apunte
15 - Recursividad