Ejercicios de Análisis de Complejidad Algorítmica - Programación 1

Acerca de¶

Estos ejercicios tienen como fin practicar el análisis asintótico de algoritmos, el uso de las notaciones Big-O, Omega y Theta, y el cálculo formal e informal del costo temporal y espacial de subprogramas iterativos y recursivos en C.

Capítulos de Apunte Correspondientes¶

Referencias y Lecturas Complementarias

Cuestiones de Estilo Aplicables¶

Medición e instrumentación: Al implementar análisis empíricos, utilizá la biblioteca <time.h> para medir tiempos físicos reales sin alterar la estructura algorítmica principal del código evaluado.

Fundamentos de Notación Asintótica¶

Ejercicio 24.1 - Simplificación de Funciones ⭐⭐☆☆☆¶

Para cada función de costo, determinar su clasificación en notación Big-O (ignorando constantes y términos de menor orden): a) $T(n) = 5n^3 + 2n^2 + 100$
b) $T(n) = 3n \log n + 2n + 50$
c) $T(n) = 2^n + n^3 + 1000n$
d) $T(n) = \log(n^2) + \sqrt{n}$
e) $T(n) = n! + 2^n + n^{10}$

Ejercicio 24.2 - Comparación de Funciones ⭐⭐☆☆☆¶

Ordenar las siguientes funciones de menor a mayor tasa de crecimiento asintótico:

\log n, \quad n^2, \quad 2^n, \quad n!, \quad n \log n, \quad \sqrt{n}, \quad n^3, \quad 1, \quad n \log^2 n, \quad 2^{2n}

(1)

Ejercicio 24.3 - Verdadero o Falso ⭐⭐☆☆☆¶

Determinar si las siguientes afirmaciones son verdaderas o falsas. Justificar. a) $n^2 + n = O(n^2)$
b) $n^2 = O(n^3)$
c) $n^3 = O(n^2)$
d) $2^n = O(3^n)$
e) $3^n = O(2^n)$
f) $\log_2 n = O(\log_{10} n)$
g) $n \log n = O(n^2)$
h) $n^2 = \Omega(n \log n)$

Ejercicio 24.4 - Demostración Formal de Big-O ⭐⭐☆☆☆¶

Demostrar formalmente que $f(n) = 3n^2 + 5n + 2$ es $O(n^2)$ encontrando constantes $c$ y $n_0$ que satisfagan la definición.

Análisis de Lazos Simples¶

Ejercicio 24.5 - Lazo Simple ⭐☆☆☆☆¶

Analizar la complejidad temporal de este código:

int suma = 0;
for (int i = 0; i < n; i++) {
    suma += i;
}

Ejercicio 24.6 - Lazo con Incremento Variable ⭐⭐☆☆☆¶

Analizar la complejidad de:

int suma = 0;
for (int i = 0; i < n; i += 2) {
    suma += i;
}

Ejercicio 24.7 - Lazo con Multiplicación ⭐⭐☆☆☆¶

Analizar la complejidad de:

int contador = 0;
for (int i = 1; i < n; i *= 2) {
    contador++;
}

Ejercicio 24.8 - Lazo con División ⭐⭐☆☆☆¶

Analizar la complejidad de:

int contador = 0;
for (int i = n; i > 1; i /= 2) {
    contador++;
}

Ejercicio 24.9 - Contar Operaciones ⭐☆☆☆☆¶

Contá cuántas operaciones ejecuta este código:

int suma = 0;
for (int i = 0; i < n; i++) {
    suma += i;
}

Orientación:

Inicialización: 1
Comparación en lazo: n+1
Incremento: n
Suma: n
Total: ~3n + 2 operaciones
Complejidad: O(n)

Ejercicio 24.10 - Analizar Lazo Anidado ⭐⭐☆☆☆¶

¿Cuál es la complejidad de este código?

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        printf("%d,%d ", i, j);
    }
}

Orientación:

Lazo externo: n iteraciones
Lazo interno: n iteraciones por cada externa
Total: n × n = n²
Complejidad: O(n²)

Ejercicio 24.11 - Comparar Algoritmos ⭐⭐☆☆☆¶

Compará la complejidad de buscar un elemento en:

Array no ordenado (búsqueda lineal)
Array ordenado (búsqueda binaria)

Orientación:

Lineal: O(n) - peor caso revisa todos
Binaria: O(log n) - divide a la mitad en cada paso
Para n=1,000,000: lineal hace ~1M comparaciones, binaria ~20

Ejercicio 24.12 - Identificar Complejidad ⭐⭐☆☆☆¶

Determiná la complejidad de cada fragmento:

int suma = 0;
for (int i = 0; i < 100; i++) {
    suma += i;
}

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        printf("%d ", i * j);
    }
}

int i = n;
while (i > 0) {
    printf("%d ", i);
    i = i / 2;
}

Orientación:

a) O(1) - cantidad fija de iteraciones
b) O(n × m) - depende de dos variables
c) O(log n) - divide por 2 cada vez

Ejercicio 24.13 - Suma de Matriz ⭐⭐⭐☆☆¶

Analizá la complejidad de sumar todos los elementos de una matriz n×m.

Orientación:

1
2
3
4
5
6
int suma = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        suma += matriz[i][j];
    }
}

Visita cada elemento una vez
n × m elementos
Complejidad: O(n × m)
Si n = m: O(n²)

Ejercicio 24.14 - Fibonacci Naive vs Optimizado ⭐⭐⭐☆☆¶

Compará complejidad de Fibonacci recursivo vs iterativo.

Orientación:

Recursivo:
```
int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}
```
- Complejidad: O(2ⁿ) - exponencial
- Árbol de recursión crece exponencialmente

Iterativo:

int fib(int n) {
    int a = 0, b = 1, temp;
    for (int i = 0; i < n; i++) {
        temp = a + b;
        a = b;
        b = temp;
    }
    return a;
}

Complejidad: O(n) - lineal

Ejercicio 24.15 - Búsqueda del Máximo ⭐⭐☆☆☆¶

Implementá función para encontrar el máximo de un array y analizá su complejidad.

Orientación:

1
2
3
4
5
6
7
int maximo(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) max = arr[i];
    }
    return max;
}

Recorre array una vez
Tiempo: O(n)
Espacio: O(1) - solo una variable

Ejercicio 24.16 - Duplicados en Array ⭐⭐⭐☆☆¶

Compará dos formas de encontrar duplicados:

Método 1: Comparar cada par

1
2
3
4
5
6
7
8
bool tiene_duplicados_1(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (arr[i] == arr[j]) return true;
        }
    }
    return false;
}

Método 2: Ordenar primero

1
2
3
4
5
6
7
bool tiene_duplicados_2(int arr[], int n) {
    qsort(arr, n, sizeof(int), comparar);  // O(n log n)
    for (int i = 0; i < n-1; i++) {
        if (arr[i] == arr[i+1]) return true;
    }
    return false;
}

Orientación:

Método 1: O(n²) tiempo, O(1) espacio
Método 2: O(n log n) tiempo, O(1) espacio (si qsort es in-place)
Para n grande, método 2 es mucho más rápido

Ejercicio 24.17 - Ordenamiento Burbuja ⭐⭐⭐☆☆¶

Analizá complejidad del ordenamiento burbuja.

Orientación:

1
2
3
4
5
6
7
8
9
void burbuja(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                intercambiar(&arr[j], &arr[j+1]);
            }
        }
    }
}

Peor caso: O(n²) - array invertido
Mejor caso: O(n²) - incluso si ya está ordenado (sin optimizar)
Optimización: Agregar flag para detectar si hubo swaps

Ejercicio 24.18 - Complejidad Espacial ⭐⭐⭐☆☆¶

Analizá memoria usada por MergeSort.

Orientación:

1
2
3
4
5
6
7
8
void merge_sort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        merge_sort(arr, l, m);
        merge_sort(arr, m+1, r);
        merge(arr, l, m, r);  // Usa array temporal
    }
}

Profundidad de recursión: O(log n)
Array temporal en merge: O(n)
Espacio: O(n) para array + O(log n) para stack de recursión = O(n)

Ejercicio 24.19 - Suma de Pares ⭐⭐⭐⭐☆¶

Encontrá dos números en array que sumen un objetivo.

Método 1: Fuerza bruta

1
2
3
4
5
6
7
8
bool suma_objetivo_1(int arr[], int n, int objetivo) {
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (arr[i] + arr[j] == objetivo) return true;
        }
    }
    return false;
}

Método 2: Con tabla hash

1
2
3
4
5
6
7
8
9
10
bool suma_objetivo_2(int arr[], int n, int objetivo) {
    hash_set_t *set = crear_set();
    for (int i = 0; i < n; i++) {
        if (contiene(set, objetivo - arr[i])) {
            return true;
        }
        insertar(set, arr[i]);
    }
    return false;
}

Orientación:

Método 1: O(n²) tiempo, O(1) espacio
Método 2: O(n) tiempo promedio, O(n) espacio
Trade-off: tiempo por espacio

Ejercicio 24.20 - Números Primos hasta N ⭐⭐⭐⭐☆¶

Compará verificar primos uno por uno vs Criba de Eratóstenes.

Método 1: Verificar cada número

// Para cada i de 2 a N:
//   Si es_primo(i): contar
// es_primo: O(√n) por cada número
// Total: O(N × √N)

Método 2: Criba

1
2
3
4
5
6
7
8
9
10
11
12
bool *criba(int n) {
    bool *es_primo = malloc((n+1) * sizeof(bool));
    // Inicializar todo en true
    for (int i = 2; i * i <= n; i++) {
        if (es_primo[i]) {
            for (int j = i * i; j <= n; j += i) {
                es_primo[j] = false;
            }
        }
    }
    return es_primo;
}

Orientación:

Criba: O(n log log n) tiempo, O(n) espacio
Mucho más eficiente para rangos grandes

Ejercicio 24.21 - Subsecuencia Común Más Larga (LCS) ⭐⭐⭐⭐⭐¶

Analizá complejidad de LCS con programación dinámica.

Orientación:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int lcs(char *X, char *Y, int m, int n) {
    int dp[m+1][n+1];
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                dp[i][j] = 0;
            else if (X[i-1] == Y[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
    return dp[m][n];
}

Tiempo: O(m × n) - llena tabla m×n
Espacio: O(m × n) - tabla DP
Optimización espacial: O(min(m, n)) con dos filas

Ejercicio 24.22 - Multiplicación de Matrices ⭐⭐⭐⭐☆¶

Analizá complejidad de multiplicar dos matrices n×n.

Orientación:

1
2
3
4
5
6
7
8
9
10
void multiplicar(int A[N][N], int B[N][N], int C[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            C[i][j] = 0;
            for (int k = 0; k < N; k++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
}

Tres lazos anidados: n × n × n
Complejidad: O(n³)
Algoritmos más eficientes existen (Strassen: O(n^2.807))

Ejercicio 24.23 - Torres de Hanoi ⭐⭐⭐⭐☆¶

Analizá complejidad de Torres de Hanoi.

Orientación:

1
2
3
4
5
6
7
8
9
void hanoi(int n, char origen, char destino, char auxiliar) {
    if (n == 1) {
        mover(origen, destino);
    } else {
        hanoi(n-1, origen, auxiliar, destino);
        mover(origen, destino);
        hanoi(n-1, auxiliar, destino, origen);
    }
}

Recurrencia: T(n) = 2T(n-1) + 1
Solución: T(n) = 2ⁿ - 1
Complejidad: O(2ⁿ) - exponencial
Cantidad mínima de movimientos

Ejercicio 24.24 - Análisis Amortizado ⭐⭐⭐⭐⭐¶

Analizá costo amortizado de inserción en vector dinámico con duplicación.

Orientación:

1
2
3
4
5
6
void agregar(vector_t *v, int elem) {
    if (v->tamanio == v->capacidad) {
        redimensionar(v, v->capacidad * 2);  // O(n)
    }
    v->datos[v->tamanio++] = elem;  // O(1)
}

Inserción simple: O(1)
Redimensionamiento: O(n)
¿Cuánto cuesta en promedio?
Análisis: Redimensionar en potencias de 2: n/2 + n/4 + n/8 + ... < n
Costo amortizado: O(1) por inserción

Ejercicio 24.25 - Comparar Estructuras de Datos ⭐⭐⭐⭐☆¶

Compará complejidad de operaciones en diferentes estructuras:

Estructura	Búsqueda	Inserción	Eliminación
Array no ordenado	O(n)	O(1) al final	O(n)
Array ordenado	O(log n)	O(n)	O(n)
Lista enlazada	O(n)	O(1) al inicio	O(1) con puntero
ABB balanceado	O(log n)	O(log n)	O(log n)
Hash table	O(1) promedio	O(1) promedio	O(1) promedio

Orientación:

Elegir estructura según operaciones más frecuentes
Trade-offs entre tiempo y espacio

Ejercicio 24.26 - Problema del Viajante (TSP) ⭐⭐⭐⭐⭐¶

Analizá complejidad de soluciones al TSP.

Fuerza Bruta:

// Probar todas las permutaciones de ciudades
// Cantidad de permutaciones: n!
// Complejidad: O(n!)

Programación Dinámica (Held-Karp):

// Estado: (ciudades visitadas, ciudad actual)
// Estados: 2ⁿ × n
// Complejidad: O(n² × 2ⁿ)

Orientación:

Problema NP-completo
O(n²2ⁿ) sigue siendo exponencial, pero mejor que O(n!)
Para n=20: 20! ≈ 10¹⁸, 20²·2²⁰ ≈ 10⁹

Ejercicio 24.27 - Optimización de Caché ⭐⭐⭐⭐⭐¶

Compará estos dos códigos para sumar matriz:

Versión 1:

for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
        suma += M[i][j];

Versión 2:

for (j = 0; j < N; j++)
    for (i = 0; i < N; i++)
        suma += M[i][j];

Orientación:

Ambos: O(N²) operaciones
Pero: Versión 1 es más rápida en la práctica
Razón: Localidad espacial (row-major order en C)
Versión 1: cache misses ~N²/L
Versión 2: cache misses ~N²
L = tamaño de línea de caché

Ejercicio 24.28 - Medir Empíricamente ⭐⭐⭐⭐⭐¶

Implementá framework para medir tiempos y validar análisis teórico.

Orientación:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <time.h>

double medir_tiempo(void (*funcion)(int*, int), int *arr, int n) {
    clock_t inicio = clock();
    funcion(arr, n);
    clock_t fin = clock();
    return (double)(fin - inicio) / CLOCKS_PER_SEC;
}

// Probar con diferentes tamaños
for (int n = 1000; n <= 100000; n *= 2) {
    double tiempo = medir_tiempo(burbuja, arr, n);
    printf("n=%d, tiempo=%.4f\n", n, tiempo);
}

Graficar tiempo vs n
Verificar si crece como n, n log n, n², etc.

Notas Finales¶

Reglas de Análisis

Sumar complejidades consecutivas:

// O(n) + O(n²) = O(n²)
for (i...) {}      // O(n)
for (i...)         // O(n²)
    for (j...) {}

Multiplicar complejidades anidadas:

// O(n) × O(log n) = O(n log n)
for (i...) {               // O(n)
    busqueda_binaria();    // O(log n)
}

Ignorar constantes y términos menores:

// 3n² + 5n + 10 = O(n²)
// n log n + n = O(n log n)

Peor caso vs caso promedio:

QuickSort: O(n²) peor, O(n log n) promedio
Hash table: O(n) peor, O(1) promedio

Errores de Análisis

Olvidar operaciones costosas dentro de lazos:

for (i...) {
    strcpy(dest, src);  // O(longitud) no O(1)
}

Confundir tiempo con espacio:
- Recursión usa espacio en stack
- Arrays temporales cuentan en espacio
Ignorar constantes ocultas:
- O(n) con constante 1000 puede ser peor que O(n²) con constante 0.001 para n pequeño
No considerar caso promedio:
- QuickSort es O(n²) peor caso pero casi siempre O(n log n)

Estas consignas desarrollan capacidad de analizar y comparar algoritmos teórica y empíricamente, esencial para diseñar soluciones eficientes.