Algoritmia y Estructuras de Datos Avanzadas · Semana 2 · Sesión 1

Complejidad y simulación

Objetivo: estimar si una idea pasa el límite de tiempo antes de programarla
Plan de la sesión

Qué vamos a ver hoy

MinTema
0–25Contar operaciones y notación O
25–40Tabla de restricciones contra complejidad
40–60Costos ocultos en Python
60–70Medir tiempos y generar casos grandes
70–90Simulación y casos borde: Permutations
Motivación

Dos soluciones correctas, un solo AC

Problema: dado un arreglo de n ≤ 2·10⁵ enteros, contar cuántos valores distintos tiene.

# Solución A
vistos = []
for x in a:
    if x not in vistos:   # recorre la lista
        vistos.append(x)
print(len(vistos))
# Solución B
print(len(set(a)))

Solución A TLE

Cada x not in vistos recorre hasta n elementos. En total son hasta n² = 4·10¹⁰ comparaciones.

Solución B AC

Insertar en un set cuesta O(1) en promedio. En total son unas 2·10⁵ operaciones.

Las dos dan la respuesta correcta. Lo que cambia es la cantidad de operaciones.

Parte 1

Contar operaciones

Cuántas veces se ejecuta cada línea en función de n.

Contar operaciones

Cada celda es una vuelta del bucle


      

      

    

    

  

  





  
Notación O

  
Las complejidades más comunes

  

    
ComplejidadNombreEjemplo

    
O(1)constanteacceder a a[i], fórmula de Gauss

    
O(log n)logarítmicabúsqueda binaria, dividir n entre 2 hasta llegar a 1

    
O(n)linealrecorrer el arreglo una vez, sum(a)

    
O(n log n)ordenar con sort

    
O(n²)cuadráticarevisar todos los pares (i, j)

    
O(2ⁿ)exponencialrevisar todos los subconjuntos

    
O(n!)factorialrevisar todas las permutaciones

  

  
Se escribe el término que más crece y sin constantes: 3n² + 5n + 7 operaciones es O(n²).






  
Calculadora

  
¿Cabe en 1 segundo?

  
n =

  

  
Supuesto: en el juez, PyPy hace unas 10⁸ operaciones simples por segundo y C++ unas 10⁹. Son órdenes de magnitud. Desde n = 10⁶ se muestra también C++. Medido en un Apple M4, C++ fue entre 1 y 9 veces más rápido que PyPy según el código. La longitud de cada barra está en escala logarítmica.

  





  
Restricciones

  
De la restricción a la complejidad

  

    

      
RestricciónComplejidad aceptable

      
n ≤ 10O(n!)

      
n ≤ 20O(2ⁿ)

      
n ≤ 500O(n³)

      
n ≤ 5000O(n²)

      
n ≤ 2·10⁵O(n log n)

      
n ≤ 10⁶ o másO(n) u O(log n)

    

    

      
La tabla viene de pedir unas 10⁸ operaciones como máximo. Para C++ es una regla con margen, porque hace entre 10⁸ y 10⁹ operaciones simples por segundo.

      
PyPy hace unas 10⁸ en bucles simples, así que usa la tabla casi sin margen. Con muchas listas pequeñas, tuplas o diccionarios es más lento, así que conviene dejar margen.

      
Uso práctico: leer las restricciones primero y descartar las ideas que no caben.

    

  

  





  
Ejercicio

  
¿Qué complejidad se necesita?

  
Haga clic en cada tarjeta para ver la respuesta.

  

  





  
Ejercicio

  
¿Cuál es la complejidad de cada fragmento?

  

    

      
for i in range(n):
    for j in range(5):
        s += a[i] * j

      
O(n). El bucle interno siempre da 5 vueltas.

      
i = n
while i > 0:
    i //= 2

      
O(log n). i se divide entre 2 en cada vuelta.

    

    

      
for i in range(n):
    if a[i] in b:      # b es una lista de tamaño n
        c += 1

      
O(n²). in sobre una lista recorre la lista.

      
a.sort()
for i in range(n):
    j = bisect_left(a, x - a[i])

      
O(n log n). Ordenar es n log n y cada bisect es log n.

    

  






  
Parte 2

  
Costos ocultos en Python

  
Operaciones que se escriben en una línea y recorren toda la lista.






  
in sobre lista frente a set

  
Buscar un valor: lista o set

  

    

      
Lista: revisa uno por uno

      

      

    

    

      
Set: calcula dónde está

      

      

      

    

  

  

  





  
pop(0) frente a deque

  
Sacar el primer elemento de una lista

  

    

      
a.pop(0) mueve todo el resto

      

      

    

    

      
d.popleft() solo mueve el inicio

      

      

    

  

  

  





  
Tabla

  
Costos ocultos más comunes

  

    

      
OperaciónCostoAlternativa

      
x in listaO(n)x in conjunto: O(1)

      
lista.pop(0)O(n)deque.popleft(): O(1)

      
lista.insert(0, x)O(n)deque.appendleft(x)

      
lista.index(x)O(n)dict de valor a posición

      
lista.count(x)O(n)Counter una sola vez

      
a[i:j]O(j − i)trabajar con índices

      
s = s + t en un bucleO(len) por vueltalista + "".join

      
min(a), sum(a)O(n)calcular una vez, fuera del bucle

    

    
Ninguna de estas operaciones es un problema si se hace una vez. El problema es hacerlas dentro de un bucle de n vueltas.

  






  
Medición

  
Cuánto cuestan en la práctica

  

    
10⁴ búsquedas en 10⁵ elementos

    
x in lista
0.25 s

    
x in conjunto
0.0004 s

    
Sacar 10⁵ elementos por el inicio

    
lista.pop(0)
0.61 s

    
deque.popleft()
0.002 s

  

  
PyPy 3.11, Apple M4. En cada par, las barras usan la misma escala.

  





  
Parte 3

  
Medir y probar

  
Comprobar el tiempo en el computador antes de enviar.






  
Medir tiempos

  
Generar un caso grande y medir

  

    

      gen.py: escribe un caso con n = 2·10⁵
      
import random
n = 200000
print(n)
print(" ".join(str(random.randint(1, 10**9))
               for _ in range(n)))

      
pypy3 gen.py > grande.txt
time pypy3 sol.py < grande.txt

    

    

      Medir una parte del código
      
import time
t0 = time.perf_counter()
# ... código a medir ...
t1 = time.perf_counter()
print(f"{t1 - t0:.3f} s", file=sys.stderr)

      
Se escribe en sys.stderr para no mezclar la medición con la salida. Hay que borrarlo antes de enviar.

    

  

  





  
Prueba aleatoria

  
Comparar con una solución lenta

  

    
import random, subprocess

for it in range(500):
    n = random.randint(1, 8)
    a = [random.randint(1, 10) for _ in range(n)]
    caso = f"{n}\n{' '.join(map(str, a))}\n"
    r1 = subprocess.run(["pypy3", "lenta.py"], input=caso,
                        capture_output=True, text=True).stdout
    r2 = subprocess.run(["pypy3", "rapida.py"], input=caso,
                        capture_output=True, text=True).stdout
    if r1 != r2:
        print("Diferencia en:\n" + caso)
        print("lenta:", r1, "rapida:", r2)
        break

    
    
      
  • La solución lenta prueba todo y es fácil de escribir bien.
    • 
      
  • Los casos son pequeños para que la lenta termine rápido.
    • 
      
  • Cuando hay diferencia, el caso que falla es corto y se puede revisar a mano.
    • 
    

  






  
Parte 4

  
Simulación

  
Hacer exactamente lo que dice el enunciado y revisar los casos borde.






  
Simulación

  
Cómo resolver un problema de simulación

  

    
    
      
  1. Escribir los pasos del enunciado en orden, en español.
    2. 
      
  2. Elegir cómo guardar el estado (variables, listas).
    3. 
      
  3. Traducir cada paso a código.
    4. 
      
  4. Contar cuántos pasos hace la simulación y comparar con la tabla.
    5. 
    

    

      
Casos borde que siempre hay que probar

      
    
        
  • n = 1 (y n = 0 si las restricciones lo permiten)
    • 
        
  • El valor máximo de n
    • 
        
  • Todos los elementos iguales
    • 
        
  • Arreglo ya ordenado y ordenado al revés
    • 
        
  • Valores máximos (10⁹, 10¹⁸)
    • 
        
  • Respuesta "imposible" o "NO"
    • 
      

    

  






  
CSES 1070 · Permutations

  
Una permutación sin vecinos consecutivos

  

    

      
Construir una permutación de 1…n donde dos vecinos nunca difieran en 1. Si no existe, imprimir NO SOLUTION. Restricción: n ≤ 10⁶.

      

        

      

    

    

      
def main():
    n = int(input())
    if n == 2 or n == 3:
        print("NO SOLUTION")
        return
    p = list(range(2, n + 1, 2)) + list(range(1, n + 1, 2))
    print(*p)

main()

      
Dos pares seguidos difieren en 2. Lo mismo dos impares. En la unión, el último par (n o n − 1) y el 1 difieren en más de 1 cuando n ≥ 4.

    

  

  





  
Sesión 2

  
Problemas de la práctica

  

    

      
CSES

      
    

    

      
Codeforces Div. 4

      
    

    

      
AtCoder (problemas B)

      
    

  

  
En Coins, la búsqueda completa hace hasta 51³ ≈ 1.3·10⁵ vueltas: cabe sin problema.






  
Resumen

  
Antes de programar

  
    
    
  1. Leer n en las restricciones y buscar la complejidad en la tabla.
    2. 
    
  2. Contar las operaciones de la idea, incluyendo los costos ocultos.
    3. 
    
  3. Si la idea no cabe, buscar otra antes de escribir código.
    4. 
    
  4. Probar con un caso grande generado y medir el tiempo.
    5. 
    
  5. Probar los casos borde.
    6.