DEV Community

Alexander Jimenez
Alexander Jimenez

Posted on

3

Notación Big O - Python

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.

Image description
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")

Enter fullscreen mode Exit fullscreen mode

Image description

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.

Heroku

Simplify your DevOps and maximize your time.

Since 2007, Heroku has been the go-to platform for developers as it monitors uptime, performance, and infrastructure concerns, allowing you to focus on writing code.

Learn More

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more