Complejidad Temporal

La eficiencia de un algoritmo se mide principalmente por cómo escala su tiempo de ejecución respecto al tamaño de la entrada. A continuación se presenta una clasificación de las complejidades temporales más comunes, ordenadas desde la más eficiente hasta la menos eficiente:

1. O(1) - Complejidad Constante

El tiempo de ejecución no depende del tamaño de los datos de entrada. La operación se realiza en un paso fijo.

datos_map = {10: "valor_A", 20: "valor_B"}

# Acceso directo mediante clave
resultado = datos_map.get(10) 
print(resultado)  # Operación inmediata sin importar el tamaño del diccionario

Característica principal: Ausencia de iteraciones dependientes del input.

2. O(log n) - Complejidad Logarítmica

El tiempo de ejecución crece logarítmicamente. En informática, la base suele ser 2, lo que implica que en cada paso el espacio de búsqueda se reduce a la mitad.

def busqueda_binaria_optimizada(coleccion, objetivo):
    inicio = 0
    fin = len(coleccion) - 1
    
    while inicio <= fin:
        centro = (inicio + fin) // 2
        valor_actual = coleccion[centro]
        
        if valor_actual == objetivo:
            return centro
        elif valor_actual < objetivo:
            inicio = centro + 1
        else:
            fin = centro - 1
    return -1

Característica principal: Duplicar los datos de entrada solo incrementa el tiempo de procesamiento en una unidad adicional.

3. O(n) - Complejidad Lineal

El tiempo de ejecución es directamente proporcional al tamaño de la entrada.

def imprimir_secuencia(limite):
    for indice in range(limite):
        print(f"Procesando elemento: {indice}")

Característica principal: Si la entrada se duplica, el tiempo de ejecución también se duplica.

4. O(n log n) - Complejidad Linealítmica

Combina una iteración lineal con una operación logarítmica en cada paso. Es común en algoritmos de ordenamiento eficientes.

def proceso_hibrido(cantidad):
    for externo in range(cantidad):          # Iteración O(n)
        interno = 1
        while interno < cantidad:            # Iteración O(log n)
            print(f"Par: {externo}, {interno}")
            interno *= 2

Característica principal: Estructura de bucle anidado donde el interno reduce el espacio exponencialmente.

5. O(n²) - Complejidad Cuadrática

Ocurre generalmente cuando hay bucles anidados donde ambos dependen del tamaño de la entrada.

def comparacion_pares(total):
    for x in range(total):            # O(n)
        for y in range(total):        # O(n)
            print(f"Comparando: {x} vs {y}")  # Total O(n²)

Si las dimensiones varía (n y m), la complejidad se denota como O(n * m).

6. O(n³) - Complejidad Cúbica

Implica tres niveles de anidamiento dependientes de la entrada. Su costo computacional es muy alto.

def operacion_triple_dimension(n):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                print(i, j, k)  # O(n³)

Advertencia: Evitar en conjuntos de datos grandes.

7. O(2ⁿ) - Complejidad Exponencial

El tiempo se duplica con cada adición a la entrada. Típico en recursividad sin optimización.

def fibonaci_recursivo(n):
    if n <= 1:
        return n
    return fibonaci_recursivo(n - 1) + fibonaci_recursivo(n - 2)

# Cada llamada genera dos nuevas ramas

Para n=10, las operaciones superan rápidamente a las de complejidad polinómica.

8. O(n!) - Complejidad Factorial

Representa la generación de todas las permutaciones posibles. Es la clase de complejidad más costosa.

from itertools import permutations

def listar_permutaciones(cantidad):
    elementos = list(range(cantidad))
    for combinacion in permutations(elementos):
        print(combinacion)  # n! iteraciones

Uso: Restringido a problemas con entradas muy pequeñas.

Complejidad Espacial

La complejidad espacial mide la cantidad de memoria adicional que requiere un algoritmo en función del tamaño de la entrada, excluyendo la memoria ocupada por los datos de entrada originales.

1. O(1) - Espacio Constante

El algorimto utiliza una cantidad fija de memoria extra, independientemente del tamaño de la entrada.

def ordenamiento_in_situ(lista):
    n = len(lista)
    for i in range(n):
        for j in range(0, n-i-1):
            if lista[j] > lista[j+1]:
                # Intercambio usando variable temporal fija
                lista[j], lista[j+1] = lista[j+1], lista[j]
    return lista

Nota: Solo se usan variables escalares para el control del flujo.

2. O(n) - Espacio Lineal

La memoria adicional requerida crece proporcionalmente con la entrada.

class ArregloDinamico:
    def __init__(self):
        self.capacidad = 1
        self.contador = 0
        self.almacen = [None] * self.capacidad

    def agregar(self, valor):
        if self.contador == self.capacidad:
            self._expandir(int(self.capacidad * 1.5))
        self.almacen[self.contador] = valor
        self.contador += 1

    def _expandir(self, nueva_capacidad):
        nuevo_almacen = [None] * nueva_capacidad
        for k in range(self.contador):
            nuevo_almacen[k] = self.almacen[k]
        self.almacen = nuevo_almacen
        self.capacidad = nueva_capacidad

Nota: Se requiere almacenar una copia o extensión de los datos originales.

3. O(n²) - Espacio Cuadrático

Se necesita memoria proporcional al cuadrdao del tamaño de la entrada, común en estructuras bidimensionales.

def generar_matriz_auxiliar(n):
    # Crea una matriz de n x n
    matriz = []
    for fila in range(n):
        nueva_fila = []
        for columna in range(n):
            nueva_fila.append(0)
        matriz.append(nueva_fila)
    return matriz  # Ocupa n * n celdas

4. O(log n) - Espacio Logarítmico

Típico en algoritmos recursivos que dividen el problema en mitades, donde la profundidad de la pila de llamadas es logarítmica.

def recursion_binaria(inicio, fin):
    if inicio >= fin:
        return
    medio = (inicio + fin) // 2
    # La pila de llamadas crece según la profundidad del árbol
    recursion_binaria(inicio, medio)
    recursion_binaria(medio + 1, fin)

Nota: La memoria se consume en el stack de llamadas, no en variables heap.