Ejercicios de Análisis de Complejidad Algorítmica

(ej_b3_c06_08)=
### Ejercicio 3.06.08 - Lazo con División Sucesiva ⭐⭐☆☆☆

:::{exercise}
:label: ej_b3_c06_08_lazo_division

Implementá una función que simule y cuantifique el número de iteraciones realizadas por un lazo con reducción por división entera a la mitad:

```c
size_t contar_divisiones_sucesivas(size_t n);
```

El lazo inicializa `i = n` y en cada paso efectúa `i /= 2` mientras `i > 1`.
Determiná formalmente su complejidad asintótica ($O(\log_2 n)$).

**Tabla de Vectores de Prueba:**

| Entrada $n$ | Secuencia de Valores de $i$ | Conteo de Iteraciones |
| :--- | :--- | :--- |
| `0` | Ninguno ($n \le 1$) | `0` |
| `1` | Ninguno ($n \le 1$) | `0` |
| `2` | $i=2$ | `1` |
| `16` | $i=16, 8, 4, 2$ | `4` |
| `32` | $i=32, 16, 8, 4, 2$ | `5` |
| `1024` | $i=1024, \dots, 2$ | `10` |

::::{solution}
```c
#include <stdio.h>
#include <stddef.h>
#include <assert.h>

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

int main(void) {
    assert(contar_divisiones_sucesivas(0) == 0);
    assert(contar_divisiones_sucesivas(1) == 0);
    assert(contar_divisiones_sucesivas(2) == 1);
    assert(contar_divisiones_sucesivas(16) == 4);
    assert(contar_divisiones_sucesivas(32) == 5);
    assert(contar_divisiones_sucesivas(1024) == 10);
    return 0;
}
```

(ej_b3_c06_09)=
## Ejercicio 3.06.09 - Contar Operaciones ⭐☆☆☆☆

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

``` c
int suma = 0;
for (int i = 0; i < n; i++)
{
    suma += i;
}
```
<!-- c -->

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

---

(ej_b3_c06_10)=
### Ejercicio 3.06.10 - Instrumentación de Lazo Anidado Cuadrático ⭐⭐☆☆☆

:::{exercise}
:label: ej_b3_c06_10_lazo_cuadratico

Implementá una función que instrumente y verifique empíricamente el conteo total de pasos de un lazo doblemente anidado:
```c
size_t contar_iteraciones_cuadraticas(size_t n);
```
El lazo recorre $i$ de $0$ a $n-1$ y $j$ de $0$ a $n-1$, demostrando que la complejidad es $O(n^2)$.

**Tabla de Vectores de Prueba:**

| Valor $n$ | Total de Pasos ($n \times n$) | Complejidad |
| :--- | :--- | :--- |
| `0` | `0` | Caso nulo |
| `1` | `1` | $1^2 = 1$ |
| `5` | `25` | $5^2 = 25$ |
| `100` | `10000` | $100^2 = 10000$ |

::::{solution}
```c
#include <stdio.h>
#include <stddef.h>
#include <assert.h>

size_t contar_iteraciones_cuadraticas(size_t n) {
    size_t pasos = 0;
    for (size_t i = 0; i < n; ++i) {
        for (size_t j = 0; j < n; ++j) {
            pasos++;
        }
    }
    return pasos;
}

int main(void) {
    assert(contar_iteraciones_cuadraticas(0) == 0);
    assert(contar_iteraciones_cuadraticas(1) == 1);
    assert(contar_iteraciones_cuadraticas(5) == 25);
    assert(contar_iteraciones_cuadraticas(100) == 10000);
    return 0;
}
```

(ej_b3_c06_11)=
### Ejercicio 3.06.11 - Comparación Empírica de Pasos: Búsqueda Lineal vs Binaria ⭐⭐☆☆☆

:::{exercise}
:label: ej_b3_c06_11_comparar_busquedas
:enumerator: complejidad-11

Implementá una función instrumentada que compare la cantidad de comparaciones elementales efectuadas por una búsqueda lineal frente a una búsqueda binaria sobre un mismo arreglo ordenado:
```c
typedef struct {
    size_t pasos_lineal;
    size_t pasos_binaria;
} comparacion_busqueda_t;

comparacion_busqueda_t comparar_pasos_busqueda(const int *arr, size_t n, int objetivo);
```
- **Búsqueda lineal:** Recorre secuencialmente desde el índice $0$; por cada elemento compara si es igual al objetivo e incrementa `pasos_lineal`. Si coincide o si `arr[i] > objetivo` (cortocircuito para arreglo ordenado), se detiene.
- **Búsqueda binaria:** Inicializa ventana `[izq, der]`. En cada iteración donde `izq <= der`, incrementa `pasos_binaria`, calcula `medio` y compara con `objetivo`.

**Nivel de Bloom:** Nivel 3 (Aplicación) y Nivel 4 (Análisis).  
**Conceptos requeridos:** Conteo de operaciones clave, divergencia asintótica $O(N)$ vs $O(\log_2 N)$.  
**Techo conceptual:** El arreglo debe estar estrictamente ordenado de menor a mayor.

#### Contrato de la Función
- **Firma:** `comparacion_busqueda_t comparar_pasos_busqueda(const int *arr, size_t n, int objetivo);`
- **Precondiciones:** Arreglo ordenado. Si $n > 0$, `arr != NULL`.
- **Postcondiciones:** Retorna una estructura con el total de comparaciones realizadas por ambos algoritmos.

#### Tabla de Vectores de Prueba

| Arreglo ($n=16$) | Objetivo | Pasos Lineal | Pasos Binaria | Justificación Técnica |
| :--- | :--- | :--- | :--- | :--- |
| `0, 1, 2, ..., 15` | `0` | `1` | $\le 4$ | Mejor caso para búsqueda lineal |
| `0, 1, 2, ..., 15` | `15` | `16` | $\le 4$ | Peor caso lineal ($O(N)$) vs acotado logarítmico |
| `0, 1, 2, ..., 15` | `99` (ausente) | `16` | $\le 5$ | Ausencia demostrada con ratio $N / \log_2 N$ |
| Vacío ($n=0$) | `42` | `0` | `0` | Caso base sin ejecuciones |

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;
}

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

1
2
3
4
5
6
7
8
9
10
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;
}

---

(ej_b3_c06_17)=
## Ejercicio 3.06.17 - Ordenamiento Burbuja ⭐⭐⭐☆☆

Analizá complejidad del ordenamiento burbuja.

**Orientación:**

```{code-block} c
:linenos:
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]);
            }
        }
    }
}
```
<!-- {code-block} c -->
- **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

---

(ej_b3_c06_18)=
## Ejercicio 3.06.18 - Complejidad Espacial ⭐⭐⭐☆☆

Analizá memoria usada por MergeSort.

**Orientación:**

```{code-block} c
:linenos:
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
    }
}
```
<!-- {code-block} c -->
- 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)

---

(ej_b3_c06_19)=
## Ejercicio 3.06.19 - Suma de Pares ⭐⭐⭐⭐☆

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

**Método 1:** Fuerza bruta

```{code-block} c
:linenos:
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;
}
```
<!-- {code-block} c -->

**Método 2:** Con tabla hash
```{code-block} c
:linenos:
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;
}
```
<!-- {code-block} c -->

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

---

(ej_b3_c06_20)=
## Ejercicio 3.06.20 - Números Primos hasta N ⭐⭐⭐⭐☆

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

**Método 1:** Verificar cada número

``` c
// Para cada i de 2 a N:
//   Si es_primo(i): contar
// es_primo: O(√n) por cada número
// Total: O(N × √N)
```
<!-- c -->

**Método 2:** Criba
```{code-block} c
:linenos:
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;
}
```
<!-- {code-block} c -->

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

---

(ej_b3_c06_21)=
## Ejercicio 3.06.21 - Subsecuencia Común Más Larga (LCS) ⭐⭐⭐⭐⭐

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

**Orientación:**

```{code-block} c
:linenos:
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];
}
```
<!-- {code-block} c -->
- **Tiempo:** O(m × n) - llena tabla m×n
- **Espacio:** O(m × n) - tabla DP
- Optimización espacial: O(min(m, n)) con dos filas

---

(ej_b3_c06_22)=
## Ejercicio 3.06.22 - Multiplicación de Matrices ⭐⭐⭐⭐☆

Analizá complejidad de multiplicar dos matrices n×n.

**Orientación:**

```{code-block} c
:linenos:
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];
            }
        }
    }
}
```
<!-- {code-block} c -->
- Tres lazos anidados: n × n × n
- **Complejidad:** O(n³)
- Algoritmos más eficientes existen (Strassen: O(n^2.807))

---

(ej_b3_c06_23)=
## Ejercicio 3.06.23 - Torres de Hanoi ⭐⭐⭐⭐☆

Analizá complejidad de Torres de Hanoi.

**Orientación:**

```{code-block} c
:linenos:
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);
    }
}
```
<!-- {code-block} c -->
- Recurrencia: T(n) = 2T(n-1) + 1
- Solución: T(n) = 2ⁿ - 1
- **Complejidad:** O(2ⁿ) - exponencial
- Cantidad mínima de movimientos

---

(ej_b3_c06_24)=
## Ejercicio 3.06.24 - Análisis Amortizado ⭐⭐⭐⭐⭐

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

**Orientación:**

```{code-block} c
:linenos:
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)
}
```
<!-- {code-block} c -->
- 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

---

(ej_b3_c06_25)=
## Ejercicio 3.06.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

---

(ej_b3_c06_26)=
## Ejercicio 3.06.26 - Problema del Viajante (TSP) ⭐⭐⭐⭐⭐

Analizá complejidad de soluciones al TSP.

**Fuerza Bruta:**

``` c
// Probar todas las permutaciones de ciudades
// Cantidad de permutaciones: n!
// Complejidad: O(n!)
```
<!-- c -->

**Programación Dinámica (Held-Karp):**
``` c
// Estado: (ciudades visitadas, ciudad actual)
// Estados: 2ⁿ × n
// Complejidad: O(n² × 2ⁿ)
```
<!-- c -->

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

---

(ej_b3_c06_27)=
## Ejercicio 3.06.27 - Optimización de Caché ⭐⭐⭐⭐⭐

Compará estos dos códigos para sumar matriz:

**Versión 1:**

``` c
for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
        suma += M[i][j];
```
<!-- c -->

**Versión 2:**
``` c
for (j = 0; j < N; j++)
    for (i = 0; i < N; i++)
        suma += M[i][j];
```
<!-- c -->

**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é

---

(ej_b3_c06_28)=
## Ejercicio 3.06.28 - Medir Empíricamente ⭐⭐⭐⭐⭐

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

**Orientación:**

```{code-block} c
:linenos:
#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);
}
```
<!-- {code-block} c -->
- Graficar tiempo vs n
- Verificar si crece como n, n log n, n², etc.

---

## Notas Finales

:::{tip} Jerarquía de Complejidades

De mejor a peor:

1. **O(1)** - Constante: acceso a array por índice
2. **O(log n)** - Logarítmica: búsqueda binaria
3. **O(n)** - Lineal: recorrer array
4. **O(n log n)** - Linealítmica: mergesort, quicksort
5. **O(n²)** - Cuadrática: burbuja, selección, dos lazos anidados
6. **O(n³)** - Cúbica: multiplicación de matrices naive
7. **O(2ⁿ)** - Exponencial: subconjuntos, fibonacci naive
8. **O(n!)** - Factorial: permutaciones, TSP brute force

**Escalabilidad:**
- Para n=1,000,000:
  - O(1): 1 operación
  - O(log n): ~20
  - O(n): ~1M
  - O(n log n): ~20M
  - O(n²): ~1T (inmanejable)