0Pricing
DSA Interview Prep · Lección

Análisis de bucles y bucles anidados

Calcule la complejidad temporal de bucles simples, bucles anidados y bucles con rangos decrecientes, como la búsqueda binaria o las iteraciones triangulares.

Análisis de bucles y bucles anidados es una lección gratuita de DSA Interview Prep en CoddyKit. Esta es la lección 2 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de DSA Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de DSA Interview Prep incluye 4 lecciones en total.

Un solo bucle: O(n)

El bucle más sencillo ejecuta su cuerpo n veces, por lo que es O(n). Un paso mayor cambia el número de iteraciones, pero no la clase de complejidad. Empiece siempre contando cuántas veces se ejecuta el cuerpo. Consulte el código.

# O(n): body runs n times
def count_ops_linear(n):
    ops = 0
    for i in range(n):
        ops += 1     # constant work
    return ops

print(count_ops_linear(100))  # 100

# Still O(n): step=2 halves count but same class
def count_ops_half(n):
    ops = 0
    for i in range(0, n, 2):
        ops += 1
    return ops

print(count_ops_half(100))    # 50  => O(n)

Bucles anidados: O(n²) y más

Dos bucles anidados, cada uno con n iteraciones, producen n x n = O(n^2); tres producen O(n^3). Sin embargo, si el bucle interno se ejecuta un número fijo de veces, el conjunto sigue siendo lineal.

def count_pairs(n):
    ops = 0
    for i in range(n):          # n iterations
        for j in range(n):      # n iterations each
            ops += 1
    return ops

print(count_pairs(10))   # 100 = 10^2
print(count_pairs(100))  # 10000 = 100^2
# Doubling n quadruples ops: classic O(n^2)

Bucle triangular: O(n²/2) = O(n²)

Cuando el bucle interno comienza en i+1, las iteraciones forman un triángulo: n(n-1)/2, que sigue siendo O(n^2) después de omitir el factor medio. Los problemas que consideran todos los pares únicos tienen este aspecto.

def count_unique_pairs(n):
    ops = 0
    for i in range(n):          # n iterations
        for j in range(i+1, n): # n-1, n-2, ..., 0
            ops += 1
    return ops

print(count_unique_pairs(10))  # 45 = 10*9/2
print(count_unique_pairs(100)) # 4950
# Still O(n^2) -- constant factor 1/2 dropped

Bucle con rango decreciente: O(log n)

Cuando la variable del bucle se divide por la mitad en cada paso, se obtiene O(log n). La pregunta clave es: ¿el rango se reduce multiplicativamente (log n) o aditivamente (n)? Consulte el código.

def count_log_ops(n):
    ops = 0
    i = n
    while i >= 1:
        ops += 1
        i //= 2   # halve each iteration
    return ops

import math
for n in [8, 16, 64, 1024]:
    ops = count_log_ops(n)
    print(f'n={n}, ops={ops}, log2={int(math.log2(n))}')
# ops tracks log2(n) closely

Bucle anidado con interior decreciente: O(n log n)

Un bucle externo que se ejecuta n veces con un bucle interno O(log n) produce O(n log n), la estructura característica de merge sort. Detectar un paso interno O(log n) es clave para analizar algoritmos de ordenación.

import math

def count_n_log_n(n):
    ops = 0
    for i in range(n):    # n iterations
        j = n
        while j >= 1:     # log n iterations
            ops += 1
            j //= 2
    return ops

for n in [8, 32, 128]:
    ops = count_n_log_n(n)
    predicted = int(n * math.log2(n))
    print(f'n={n}: actual={ops}, n*log2(n)~={predicted}')

Bucles internos dependientes

Cuando el rango del bucle interno depende del índice externo, cuente las iteraciones totales, no las de cada paso. Un bucle interno que recorre 0..i suma n(n-1)/2 = O(n^2). Consulte el código.

# Inner loop runs i times: total = 0+1+2+...+(n-1) = n(n-1)/2 => O(n^2)
def sum_inner_i(n):
    ops = 0
    for i in range(n):
        for j in range(i):   # runs 0,1,2,...,n-1 times
            ops += 1
    return ops

print(sum_inner_i(10))  # 45 = 10*9/2  => O(n^2)

# Inner loop runs n/i times (i doubles): sum ≈ n*log n => O(n log n)
def sum_inner_n_over_i(n):
    ops = 0
    i = 1
    while i <= n:
        for j in range(n // i):
            ops += 1
        i *= 2
    return ops
print(sum_inner_n_over_i(64))  # ~ 64*6 = 384

Análisis de bubble sort paso a paso

Bubble sort realiza n(n-1)/2 comparaciones, por lo que es O(n^2). Incluso con una salida anticipada, una entrada ordenada al revés sigue necesitando todas las comparaciones. Es demasiado lento para entradas grandes.

def bubble_sort(arr):
    n = len(arr)
    comparisons = 0
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            comparisons += 1
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped:  # early exit if sorted
            break
    return comparisons

arr = list(range(10, 0, -1))  # worst case: reversed
ops = bubble_sort(arr)
print(f'Sorted: {arr}')
print(f'Comparisons: {ops}')  # 45 = 10*9/2

Bucles sobre cadenas y subcadenas

Tenga cuidado: el slicing de Python es O(k), no gratuito, y concatenar cadenas con + dentro de un bucle es O(n^2), porque se copia todo en cada iteración. Utilice ''.join(parts) en su lugar. Consulte el código.

# O(n^2): string concat in loop
def build_bad(n):
    s = ''
    for i in range(n):
        s += str(i)  # copies s each time!
    return s

# O(n): join is a single pass
def build_good(n):
    parts = []
    for i in range(n):
        parts.append(str(i))
    return ''.join(parts)

print(build_good(10))  # '0123456789'

Múltiples parámetros de entrada

Con dos entradas, la complejidad puede utilizar ambas: O(m + n) para trabajo separado y O(m x n) para trabajo anidado. En grafos, suele expresarse como O(V + E). Nombre cada variable con claridad.

# O(m + n): two independent loops
def independent(m, n):
    a = sum(range(m))  # O(m)
    b = sum(range(n))  # O(n)
    return a + b       # total O(m + n)

# O(m * n): nested
def nested(m, n):
    count = 0
    for i in range(m):     # O(m)
        for j in range(n): # O(n) each
            count += 1
    return count  # O(m * n)

print(independent(5, 10))  # 10 + 45 = 55
print(nested(5, 10))       # 50

Bucles anidados frente a llamadas secuenciales

Una llamada a una función no es gratuita: también cuenta su bucle interno. Si llama n veces a una función auxiliar O(n), obtiene O(n^2). Al analizar el código, examine siempre el interior de las llamadas opacas.

# Naive string matching: O(n*m)
def naive_search(text, pattern):
    n, m = len(text), len(pattern)
    matches = []
    for i in range(n - m + 1):  # O(n)
        if text[i:i+m] == pattern:  # O(m) comparison + O(m) slice
            matches.append(i)
    return matches
# Total: O(n*m)

print(naive_search('abcabcabc', 'abc'))  # [0, 3, 6]

Práctica: identificar la complejidad de un vistazo

Adquiera este hábito: cuente los niveles de anidamiento de los bucles, compruebe si el bucle interno depende del externo y busque costes ocultos en las llamadas a funciones y en el slicing. El código plantea un rompecabezas para que lo intente.

# What is the complexity of this function?
def mystery(nums):
    result = []
    for i in range(len(nums)):          # O(n)
        for j in range(i, len(nums)):   # O(n) worst
            if sum(nums[i:j+1]) == 0:   # O(n) slice + sum!
                result.append((i, j))
    return result
# Answer: O(n^3)  -- three nested n-proportional ops
# Outer O(n) x inner O(n) x sum/slice O(n) = O(n^3)

Comprobación rápida

Comprobación rápida: compruebe cuánto ha retenido de las técnicas para analizar bucles. Confíe en su razonamiento. 💪

Resumen de la lección

Resumen: los bucles anidados se multiplican y los independientes se suman; un bucle interno que reduce el rango a la mitad produce O(n log n), y también deben contarse los costes ocultos dentro de las llamadas y del slicing.

Preguntas frecuentes

¿La lección «Análisis de bucles y bucles anidados» es gratis?

Sí — el texto completo de «Análisis de bucles y bucles anidados» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de DSA Interview Prep, actualiza a CoddyKit PRO. El curso de DSA Interview Prep incluye 4 lecciones en total.

¿Qué aprenderé en «Análisis de bucles y bucles anidados»?

Calcule la complejidad temporal de bucles simples, bucles anidados y bucles con rangos decrecientes, como la búsqueda binaria o las iteraciones triangulares. Practicas DSA Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.

¿Necesito experiencia previa para empezar DSA Interview Prep?

No se requiere experiencia previa. DSA Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 2 de 4.

¿Cuánto tiempo toma la lección «Análisis de bucles y bucles anidados»?

La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.

¿Puedo escribir y ejecutar código en esta lección de DSA Interview Prep?

Sí. Cada lección de DSA Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.

Todas las lecciones de este curso

  1. Notación Big-O desde cero
  2. Análisis de bucles y bucles anidados
  3. Recursión y método del árbol de recursión
  4. Complejidad espacial y compensaciones
← Volver a DSA Interview Prep