14. Complejidad algorítmica#

(★☆☆, ★★☆, ★★★) Esta notación indica la dificultad de cada ejercicio, de menor a mayor.

★☆☆ Responda las siguientes preguntas conceptuales:
1. ¿Qué mide la complejidad temporal de un algoritmo? ¿Por qué es útil analizarla?
2. ¿Por qué se usa \(n\) para describir la complejidad en lugar de un número concreto?
3. ¿Qué significa que un algoritmo sea \(O(1)\)? Dé un ejemplo.
4. ¿Cuál es la diferencia entre analizar el peor caso, el caso promedio y el mejor caso?
★☆☆ Ordene las siguientes complejidades de menor a mayor (de más eficiente a menos eficiente), y grafique (sin demasiada precisión) cómo crecen a medida que n aumenta: \(O(n^2), \quad O(1), \quad O(n!), \quad O(\log n), \quad O(n), \quad O(2^n), \quad O(n \log n)\)
★☆☆ Para cada par de complejidades, indique cuál domina a medida que n crece hacia el infinito:
1. \(O(n)\) vs \(O(n^2)\)
2. \(O(\log n)\) vs \(O(n)\)
3. \(O(n^2)\) vs \(O(n^3)\)
4. \(O(2^n)\) vs \(O(n^{100})\)
Dominancia

Decimos que \(f(n)\) domina a \(g(n)\) si \(f(n)\) crece más rápido. El algoritmo con la función dominante es el menos eficiente para valores grandes de n.
★☆☆ Indique si cada una de las siguientes afirmaciones es verdadera o falsa. Justifique su respuesta.
1. Un algoritmo \(O(n)\) siempre es más rápido que uno \(O(n^2)\) para cualquier entrada.
2. Si un programa tiene dos bucles for anidados, su complejidad es siempre \(O(n^2)\).
3. La notación Big-O describe el peor caso de un algoritmo.
4. \(O(3n + 100)\) es equivalente a \(O(n)\).
5. \(O(n^2 + n)\) es equivalente a \(O(n^2)\).
★☆☆ Encuentre la función de costo temporal \(T(n)\) del siguiente código, donde n es el tamaño de la lista data. Luego determine su complejidad Big-O.
```
def suma_elementos(data: list):
    total = 0
    for e in data:
        total += e
    return total
```
★☆☆ Encuentre \(T(n)\) y la complejidad Big-O del siguiente código. ¿Cambia la complejidad si la lista tiene 10 o 10.000 elementos?
```
def primero_y_ultimo(data: list):
    primero = data[0]
    ultimo = data[-1]
    return primero, ultimo
```
★☆☆ Encuentre \(T(n)\) y la complejidad Big-O del siguiente código, donde n es el tamaño de data. Considere que len() y range() toman tiempo constante.
```
def dos_recorridos(data: list):
    x = 0
    for e in data:
        x += e
    for e in data:
        x -= e
    return x
```
- ¿Dos bucles for secuenciales son \(O(2n)\) u \(O(n)\)? ¿Por qué?

★★☆ Encuentre \(T(n)\) y la complejidad Big-O del siguiente código. Considere que len() y range() toman tiempo constante.

def ejemplo(data: list):
    x = 0
    for e in data:
        for j in range(len(data)):
            x += e + j
    for k in range(len(data)):
        for l in range(len(data)):
            for m in range(10):
                x += 1
    for p in range(1000):
        x += 1
    return x

Identifique cada bloque de código y su costo por separado.
¿Qué término de \(T(n)\) domina? ¿Por qué los demás se descartan en Big-O?

★★☆ Encuentre \(T(n)\) y la complejidad Big-O del siguiente código, donde \(n\) es el valor del número entero recibido (no el tamaño de una lista).
```
def divisores(n: int):
    resultado = []
    for i in range(1, n + 1):
        if n % i == 0:
            resultado.append(i)
    return resultado
```
- ¿Cambiaría algo si el bucle llegara hasta n // 2 en lugar de n? ¿Por qué?
★★☆ Analice el siguiente código. \(n\) es el tamaño de data. Encuentre \(T(n)\) y la complejidad Big-O.
```
def busqueda_lineal(data: list, objetivo):
    for i in range(len(data)):
        if data[i] == objetivo:
            return i
    return -1
```
- ¿Cuál es el mejor caso? ¿Y el peor caso?
- ¿La complejidad Big-O que encontró corresponde al mejor o al peor caso?
★★☆ Analice el siguiente código. \(n\) es el tamaño de data (asuma que está ordenada de menor a mayor). Encuentre \(T(n)\) en el peor caso y determine la complejidad Big-O.
```
def busqueda_binaria(data: list, objetivo):
    izq = 0
    der = len(data) - 1
    while izq <= der:
        mid = (izq + der) // 2
        if data[mid] == objetivo:
            return mid
        elif data[mid] < objetivo:
            izq = mid + 1
        else:
            der = mid - 1
    return -1
```
Ayuda:

En cada iteración, el espacio de búsqueda se divide a la mitad. Si empezamos con n elementos, ¿cuántas veces podemos dividir por 2 antes de llegar a 1?
- ¿Cómo se compara la complejidad de la búsqueda binaria con la lineal? ¿Para qué tamaños de entrada importa la diferencia?

★★☆ Se tienen dos funciones que resuelven el mismo problema: determinar si hay algún elemento repetido en una lista.

def tiene_repetidos_v1(data: list) -> bool:
    for i in range(len(data)):
        for j in range(i + 1, len(data)):
            if data[i] == data[j]:
                return True
    return False

def tiene_repetidos_v2(data: list) -> bool:
    vistos = set()
    for e in data:
        if e in vistos:
            return True
        vistos.add(e)
    return False

Determine la complejidad Big-O de cada versión (considere que la operación e in vistos sobre un set toma tiempo \(O(1)\)).
¿Cuál elegiría para una lista de 1.000.000 de elementos? ¿Y para una de 5 elementos?

★★☆ Escriba una función que tenga exactamente la complejidad indicada para cada caso. La función puede hacer cualquier cosa con los datos, siempre que la complejidad sea correcta.
1. \(O(1)\): una función que recibe una lista y devuelve algún resultado.
2. \(O(n)\): una función que recibe una lista y devuelve algún resultado.
3. \(O(n^2)\): una función que recibe una lista y devuelve algún resultado.
★★★ Se tiene el siguiente código que busca los pares de elementos de una lista cuya suma es igual a un objetivo dado.
```
def pares_con_suma(data: list, objetivo: int):
    resultado = []
    for i in range(len(data)):
        for j in range(i + 1, len(data)):
            if data[i] + data[j] == objetivo:
                resultado.append((data[i], data[j]))
    return resultado
```
- Determine la complejidad Big-O de esta función.
- Proponga una versión más eficiente usando un set o un dict. ¿Cuál es la complejidad de su versión mejorada?
Ayuda

Para cada elemento e en data, ¿qué valor necesitaría encontrar para que la suma sea igual al objetivo?
★★★ El siguiente código implementa el algoritmo de ordenamiento Bubble Sort.
```
def bubble_sort(data: list):
    n = len(data)
    for i in range(n):
        for j in range(0, n - i - 1):
            if data[j] > data[j + 1]:
                data[j], data[j + 1] = data[j + 1], data[j]
```
- Encuentre \(T(n)\) exacta contando operaciones. ¿Cuántas comparaciones se hacen en total?
- Determine la complejidad Big-O.
- ¿Cuál es el mejor caso? ¿Cambia la complejidad Big-O si la lista ya está ordenada? ¿Se le ocurre alguna mejora para ese caso?
★★★ Dado el siguiente fragmento de código, \(n\) representa el valor del entero recibido (no un tamaño de lista).
```
def misterio(n: int):
    resultado = 0
    i = n
    while i > 1:
        resultado += i
        i = i // 2
    return resultado
```
- Trace manualmente la ejecución para n = 16 y anote el valor de i en cada iteración.
- Encuentre \(T(n)\) y determine la complejidad Big-O.
- ¿Qué relación tiene este patrón con la búsqueda binaria?
★★★ A continuación se muestra una función recursiva:
```
def suma_recursiva(data: list):
    if len(data) == 0:
        return 0
    return data[0] + suma_recursiva(data[1:])
```
- ¿Cuántas llamadas recursivas se hacen para una lista de tamaño \(n\)?
- ¿Cuál es la complejidad Big-O?
- Considere que en Python data[1:] crea una copia de la lista. ¿Afecta esto al análisis de complejidad?
★★★ Un estudiante escribe el siguiente programa para encontrar el elemento máximo de una matriz cuadrada de \(n \times n\):
```
def maximo_matriz(matriz: list):
    max_val = matriz[0][0]
    for fila in matriz:
        for elemento in fila:
            if elemento > max_val:
                max_val = elemento
    return max_val
```
- ¿Cuál es la complejidad Big-O si \(n\) representa la cantidad de filas (y columnas) de la matriz?
- ¿Cuál es la complejidad si \(n\) representa la cantidad total de elementos en la matriz?
- ¿Por qué es importante aclarar qué representa \(n\) al enunciar la complejidad de un algoritmo?