Publicado · en mejora
Algorithm
Aprende a analizar con la notación Big O cómo crecen el tiempo y la memoria de un algoritmo según el tamaño de la entrada, y a comprobarlo midiendo.
El análisis de complejidad describe cuánto crecen el tiempo y la memoria que necesita un algoritmo a medida que aumenta su entrada. En lugar de segundos, que dependen del hardware y del lenguaje, cuenta las operaciones básicas en función del tamaño de la entrada n y conserva solo el término dominante. El resultado se expresa con notación asintótica: Big O para una cota superior, Big Omega para una cota inferior y Big Theta para una cota ajustada.
Es importante porque, cuando los datos crecen, la diferencia entre órdenes de crecimiento supera a cualquier factor constante. Una rutina O(n²) que funciona bien con mil elementos puede tardar horas con un millón, mientras que una O(n log n) termina en segundos. La complejidad sirve para elegir estructuras de datos, interpretar los límites de entrada de un problema de programación, detectar costes ocultos en una revisión de código y estimar si un sistema escalará.
Empieza contando operaciones en bucles sencillos y aprendiendo las clases habituales: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ) y O(n!). Después pasa a los casos mejor, promedio y peor, al análisis amortizado, a la complejidad espacial y a resolver recurrencias con el teorema maestro. Comprueba siempre tu razonamiento con un experimento de duplicación: mide el código con n y con 2n y compara la proporción.
O, Ω y Θ dan cotas superiores, inferiores y ajustadas del crecimiento, ignorando constantes y términos de menor orden.
Los bloques consecutivos suman su coste, los bucles anidados lo multiplican y, si cada paso reduce el problema a la mitad, aparece un logaritmo.
Promedia el coste a lo largo de una secuencia de operaciones; por eso añadir a un array dinámico es O(1) aunque a veces haya que copiarlo entero.
La memoria auxiliar y la profundidad de recursión también cuentan, y el teorema maestro resuelve las recurrencias de divide y vencerás.
El script resuelve el mismo problema de dos formas: revisando todos los pares o recorriendo la lista una vez y guardando en un diccionario los valores ya vistos. Al medir ambas con timeit para n = 500, 1.000 y 2.000, cada duplicación hace la versión cuadrática unas cuatro veces más lenta y la lineal unas dos.
complexity.py
import timeit
def two_sum_quadratic(nums, target):
"""O(n^2): try every pair."""
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return i, j
return None
def two_sum_linear(nums, target):
"""O(n) on average: remember values already seen."""
seen = {}
for j, x in enumerate(nums):
i = seen.get(target - x)
if i is not None:
return i, j
seen.setdefault(x, j)
return None
print(two_sum_quadratic([8, 3, 11, 5, 2], 13), two_sum_linear([8, 3, 11, 5, 2], 13))
for n in (500, 1_000, 2_000):
nums = list(range(0, 2 * n, 2)) # even numbers only, so no pair sums to -1
slow = timeit.timeit(lambda: two_sum_quadratic(nums, -1), number=3) / 3
fast = timeit.timeit(lambda: two_sum_linear(nums, -1), number=3) / 3
print(f"n={n:>5} O(n^2) {slow * 1000:8.2f} ms O(n) {fast * 1000:6.3f} ms")
python complexity.pySeis capítulos que te llevan desde la instalación hasta las ideas clave de Análisis de complejidad.
Haz preguntas, comparte tu experiencia e intercambia opiniones sobre Análisis de complejidad.
Todavía no hay debates. Empieza el primero.
0 comentarios
Iniciar sesión · Inicia sesión para dejar un comentario.
Sé el primero en comentar.