Ejercicios Prácticos de Complejidad Algorítmica I

Esta sección práctica consolida el análisis de complejidad asintótica mediante el análisis paso a paso de bucles simples, anidados y reducciones logarítmicas en múltiples lenguajes de programación.

1. Guía Rápida para el Análisis de Complejidad Temporal #

Para determinar la notación Big-O de cualquier bloque de código:

1. Bucles Simples ($O(n)$): Si un bucle recorre de $0$ a $n$ con un incremento constante ($i++$), el coste es lineal.
2. Bucles Anidados ($O(n^2)$, $O(n \times m)$): Si un bucle interno depende de las iteraciones del bucle externo, se multiplican sus órdenes de magnitud.
3. Divisiones o Multiplicaciones del Índice ($O(\log n)$): Si la variable de control se multiplica ($i *= 2$) o divide ($i /= 2$) en cada paso, el número de iteraciones es logarítmico.
4. Constantes ($O(1)$): Operaciones aritméticas directas y acceso por índice a arrays.

2. Ejercicios Resueltos de Ejemplo #

1# Caso 1: Bucle con salto logarítmico -> O(log n)
2def ejemplo_logaritmico(n):
3    i = 1
4    while i < n:
5        print(i)
6        i *= 2
7
8  # Caso 2: Bucles dependientes -> O(n^2)
9def ejemplo_triangular(n):
10    for i in range(n):
11        for j in range(i, n):
12            print(i, j)