Notación Big O - Python

Alexander Jimenez — Sat, 16 Nov 2024 17:01:20 +0000

1. Definición

Notación matemática que describe el límite superior del tiempo de ejecución o el uso de espacio de un algoritmo. Se denota como O(f(n)), donde f(n) es una función que representa el tiempo o espacio en función del tamaño de la entrada n.

Mas información visita: http://bigocheatsheet.com

2. Propósito

Comparación de Algoritmos: Permite comparar diferentes algoritmos y elegir el más eficiente para un problema dado.
Escalabilidad: Ayuda a predecir cómo se comportará un algoritmo cuando la cantidad de datos aumenta.

3. Análisis de Complejidad

Peor Caso: Se refiere al escenario donde el algoritmo tarda más tiempo o usa más recursos. Big O generalmente se refiere a este caso.
Mejor Caso y Caso Promedio: Aunque son importantes, se utilizan menos frecuentemente para la notación Big O.

4. Espacio vs. Tiempo

Complejidad Temporal: Se refiere al tiempo que tarda un algoritmo en ejecutarse.
Complejidad Espacial: Se refiere a la cantidad de memoria adicional que utiliza. Puede tener notaciones como O(1) (espacio constante) o O(n) (espacio lineal).

Ejemplo:

import timeit
import matplotlib.pyplot as plt
import cProfile

# O(1)


def constant_time_operation():
    return 42

# O(log n)


def logarithmic_time_operation(n):
    count = 0
    while n > 1:
        n //= 2
        count += 1
    return count

# O(n)


def linear_time_operation(n):
    total = 0
    for i in range(n):
        total += i
    return total

# O(n log n)


def linear_logarithmic_time_operation(n):
    if n <= 1:
        return n
    else:
        return linear_logarithmic_time_operation(n - 1) + n

# O(n^2)


def quadratic_time_operation(n):
    total = 0
    for i in range(n):
        for j in range(n):
            total += i + j
    return total

# O(2^n)


def exponential_time_operation(n):
    if n <= 1:
        return 1
    else:
        return exponential_time_operation(n - 1) + exponential_time_operation(n - 1)

# O(n!)


def factorial_time_operation(n):
    if n == 0:
        return 1
    else:
        return n * factorial_time_operation(n - 1)

# Function to measure execution time using timeit

def measure_time(func, *args):
    execution_time = timeit.timeit(lambda: func(*args), number=1000)
    return execution_time


def plot_results(results):
    functions, times = zip(*results)

    colors = ['skyblue', 'orange', 'green', 'red', 'purple', 'brown', 'pink']
    plt.figure(figsize=(14, 8))
    plt.bar(functions, times, color=colors)

    for i, v in enumerate(times):
        plt.text(i, v + 0.5, f"{v:.6f}", ha='center',
                 va='bottom', rotation=0, color='black')

    plt.xlabel('Function Complexity')
    plt.ylabel('Average Time (s)')
    plt.title('Execution Time of Different Algorithm Complexities')
    plt.grid(axis='y', linestyle='--', linewidth=0.5, color='gray', alpha=0.5)

    plt.tight_layout()
    plt.show()


def main():
    results = []
    results.append(("O(1)", measure_time(constant_time_operation)))
    results.append(("O(log n)", measure_time(logarithmic_time_operation, 10)))
    results.append(("O(n)", measure_time(linear_time_operation, 10)))
    results.append(("O(n log n)", measure_time(
        linear_logarithmic_time_operation, 10)))
    results.append(("O(n^2)", measure_time(quadratic_time_operation, 7)))
    results.append(("O(2^n)", measure_time(exponential_time_operation, 7)))
    results.append(("O(n!)", measure_time(factorial_time_operation, 112)))

    plot_results(results)


if __name__ == '__main__':
    cProfile.run("main()", sort="totime", filename="output_profile.prof")

Recordar que no solo basta con aplicar notación big o si bien este es el primer paso existe otras formas de optimizar en memoria ejemplo el uso de slots, cache, hilos, paralelismo, procesos etc.

Gracias por leer !!
Apóyame reaccionando e opinando.

DEV Community: Alexander Jimenez

Notación Big O - Python

1. Definición

2. Propósito

3. Análisis de Complejidad

4. Espacio vs. Tiempo