¿Cómo evaluar la complejidad de un algoritmo o…

Para evaluar la complejidad de un algoritmo, se utiliza el análisis asintótico, que permite describir la eficiencia del algoritmo en función del tamaño de los datos de entrada ($n$). Los pasos principales:

Definición de operaciones básicas: Se identifican las operaciones cuyo tiempo de ejecución depende significativamente de $n$ (por ejemplo, comparaciones, asignaciones, operaciones aritméticas).
Cálculo del número de operaciones: Se determina la cantidad de operaciones básicas en función de $n$. Esto puede ser una fórmula exacta o una estimación.
Determinación de la clase asintótica: Se utilizan las notaciones Big O ($O$), Omega ($\Omega$) y Theta ($\Theta$) para describir el comportamiento asintótico superior, inferior y exacto, respectivamente.
- $O(f(n))$: El algoritmo se ejecuta en tiempo no superior a una constante multiplicada por $f(n)$ para grandes $n$. Se usa para describir el peor caso.
- $\Omega(f(n))$: El algoritmo se ejecuta en tiempo no inferior a una constante multiplicada por $f(n)$ para grandes $n$. Se usa para describir el mejor caso.
- $\Theta(f(n))$: El algoritmo se ejecuta en tiempo proporcional a $f(n)$ para grandes $n$. Se usa para describir el caso promedio o cuando el mejor y peor caso tienen el mismo orden asintótico.

El uso más frecuente es la Gran O ($O$) para describir la cota superior del tiempo de ejecución, importante para entender la escalabilidad del algoritmo en el peor escenario.

Omisión de constantes y términos menores: Al determinar la notación asintótica, se ignoran los multiplicadores constantes y los términos de menor orden, ya que para grandes $n$ domina la función con el mayor exponente. Por ejemplo, para $3n^2 + 5n + 10$, la notación asintótica será $O(n^2)$.

Clases asintóticas típicas (en orden de menor a mayor complejidad):

$O(1)$: Complejidad constante (el tiempo de ejecución no depende de $n$).
$O(\log n)$: Complejidad logarítmica (el tiempo crece muy lentamente con $n$, típico en algoritmos de búsqueda binaria).
$O(n)$: Complejidad lineal (el tiempo es proporcional a $n$, típico en búsquedas lineales simples).
$O(n \log n)$: Complejidad lineal-logarítmica (típico en algoritmos de ordenamiento eficientes como Quick Sort o Merge Sort).
$O(n^2)$: Complejidad cuadrática (el tiempo crece con el cuadrado de $n$, típico en algoritmos de ordenamiento simples como Bubble Sort).
$O(n^c)$ (para $c > 1$): Complejidad polinómica.
$O(c^n)$ (para $c > 1$): Complejidad exponencial (el tiempo crece muy rápidamente con $n$, típico en búsqueda exhaustiva).
$O(n!)$: Complejidad factorial (el más alto, crece extremadamente rápido).

Para determinar la complejidad asintótica de estructuras cíclicas:

Bloques de código secuenciales: Se suman las complejidades. $O(A+B) = O(\max(A, B))$.
Bucles anidados: Se multiplican las cantidades de iteraciones. Un ciclo con $n$ iteraciones dentro de otro con $m$ iteraciones tiene complejidad $O(n \times m)$. Si $m=n$, entonces $O(n^2)$.
Ciclos con reducción del tamaño de entrada: Por ejemplo, dividir entre 2 en cada iteración lleva a una complejidad logarítmica ($O(\log n)$).

Ejemplo:

Recorrido simple de un array:

# Recuento de operaciones básicas (comparaciones, asignaciones)
# La operación principal es la comparación en el ciclo
def find_max(arr):
    if not arr:
        return None
    max_val = arr[0]  # 1 asignación (fuera del ciclo)
    for i in range(1, len(arr)): # El ciclo se ejecuta n-1 veces
        # Dentro del ciclo:
        # 1 comparación (if arr[i] > max_val)
        # potencialmente 1 asignación (max_val = arr[i])
        if arr[i] > max_val:
            max_val = arr[i]
    return max_val

Si el tamaño del array es $n = \texttt{len(arr)}$, el ciclo se ejecuta $n-1$ veces. En cada iteración, se realizan operaciones constantes. El número total de operaciones es proporcional a $n$. Complejidad asintótica: $O(n)$.

Ejemplo: Ordenamiento por inserción (Insertion Sort)

# Recuento de operaciones básicas
# Operaciones principales: comparaciones y asignaciones/movimientos de elementos
def insertion_sort(arr):
    # El ciclo externo se ejecuta en $n-1$ ocasiones
    for i in range(1, len(arr)):
        key = arr[i] # 1 asignación
        j = i - 1 # 1 asignación
        # El ciclo interno en el peor caso se ejecuta $i$ veces
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j] # 1 asignación (movimiento)
            j -= 1 # 1 resta y 1 asignación
        arr[j + 1] = key # 1 asignación

El ciclo externo se ejecuta $n-1$ veces. En el peor caso (el array está en orden inverso), el ciclo interno se ejecuta en promedio $i$ veces (o hasta $i$ veces). La suma de operaciones en todas las iteraciones del ciclo externo es aproximadamente $1 + 2 + ... + (n-1) \approx n^2/2$. Complejidad asintótica: $O(n^2)$ en el peor y promedio, $O(n)$ en el mejor caso (array ya ordenado). Al evaluar la complejidad, generalmente se considera el peor caso (Gran $O$).

¿Cómo evaluar la complejidad de un algoritmo o determinar su asintótica?