8 min read Articulos

Evalúa y optimiza tu código con la notación Big O — Introducción

Evalúa y optimiza tu código con la notación Big O — Introducción
¡Aprende la notación Big O y mejorar la eficiencia de tus algoritmos!, descubre cómo Big O te ayudará a optimizar tu código y su rendimiento

Sumario:

  1. 🤓 ¿Qué es la notación Big O?
  2. 🤔¿Por qué deberías aprenderlo?
  3. 📝 Ejemplos de la notación Big O en Python
  4. ✍️ Ejercicios
  5. 😎 Conclusión


🤓 ¿Qué es la notación Big O?

Bueno, la notación Big O es una notación matemática, que se utiliza para medir la eficiencia y complejidad de un algoritmo, esto lo hace calculando el tiempo necesario para ejecutarlo basándose en el peor de los casos en relación con el tamaño de su entrada.

La notación Big O se representa mediante la letra O seguida de un paréntesis que contiene una variable n que representa el tamaño de la entrada del algoritmo.

Representación Big O : O(n)

Por ejemplo, si un algoritmo tiene una complejidad O(n), significa que su tiempo de ejecución crece proporcionalmente al tamaño de la entrada. Esto quiere decir que si el tamaño de la entrada se duplica, pues el tiempo de ejecución también se duplica, fácil, ¿no es así? 😁.

El objetivo de la notación Big O es la de facilitar la elección o construcción de un algoritmo con la complejidad O(n) más baja posible, ya que esto significa que el algoritmo es más eficiente.

Además, la notación Big O se utiliza para comparar diferentes algoritmos y determinar cuál es el mejor para una tarea específica. je, je, je espero haberme dado a entender 😉.


🤔 ¿Por qué deberías aprenderlo?

En este punto, ya comprendiendo mejor que es la notación Big O , la pregunta surge.

¿Por qué debería aprender a utilizar la notación Big O?

Bueno, aprender la notación Big O tiene varios beneficios, entre ellos te puede ayudar a:

  1. Aumenta la habilidad para diseñar algoritmos: Se pueden crear programas más eficientes y optimizados para distintas situaciones.
  2. Hace más fácil la selección de algoritmos: Conociendo el rendimiento de diferentes algoritmos, se puede elegir el mejor para un problema específico.
  3. Ayuda a comprender la complejidad temporal: Se entiende mejor cómo el tamaño de la entrada afecta el tiempo de ejecución del algoritmo.
  4. Aumenta la habilidad para analizar: Se puede evaluar el rendimiento de algoritmos existentes y proponer mejoras.

Genial, ¿no lo crees?, este tipo de conocimiento, el conocer de complejidad algorítmica es más de ingenieros seniors, por lo que te puede apoyar para crecer en tu carrera profesional, ya que podrás aportar conocimiento o tomar decisiones desde puntos que pueden ser críticos como la eficiencia en los proyectos que estés involucrado 💪.


📝 Ejemplos de cómo usar la notación Big O en Python

En esta sección te mostraré unos ejemplos sencillos en Python que puedes copiar y pegar para probar, de las expresiones más básicas que nos podemos encontrar en nuestro día a día como desarrolladores de software.

Los ejemplos que veremos son los siguientes y podemos verlos en la imagen inferior que ilustra de manera sencilla la complejidad de un algoritmo a través de la notación Big O y como esta se comporta en tiempo de ejecución dependiendo del tamaño de la entrada.

O(1): Tiempo constante

Significa que el tiempo que tarda el algoritmo en completarse no se ve afectado por el tamaño de la entrada. Un ejemplo sencillo de esto sería buscar un elemento en una arreglo usando un índice para encontrarlo.

def constant_time(array):
    return array[0]
    
array = [11,82,43,74,95]
number = constant_time(array)

En resumen, la función siempre tardará la misma cantidad de tiempo en ejecutarse, lo que convierte la función (algoritmo) en una complejidad constante O(1).

O(log x): Tiempo logarítmico

Los algoritmos con una complejidad logarítmica son altamente eficientes, ya que su tiempo de ejecución crece de manera gradual con el tamaño de la entrada.

Un ejemplo de un algoritmo con complejidad logarítmica es la búsqueda binaria.

def binary_search(array, n):
	low = 0
    high = len(arr) - 1
    while low <= high:
    	mid = (low + high) // 2
		if arr[mid] == n:
			return mid
        elif arr[mid] < n:
        	low = mid + 1
        else:
        	high = mid - 1
    return -1

array = [1,2,3,4,5,6,7,8,9,10]
number = binary_search(array, 7)

En este ejemplo, la función binary_search recibe un elemento (n) a buscar y una lista ordenada (array), utilizando un enfoque de dividir y conquistar en cada iteración el bucle whiledivide la lista en dos partes y descarta la parte que no contiene el elemento buscado.

La complejidad de este algoritmo es O(log x), ya que en cada iteración, el tamaño de la lista se divide a la mitad y, en promedio, se necesitan O(log x)iteraciones para encontrar el elemento buscado.

En resumen, ⁣O(log x)se refiere a algoritmos que tienen un tiempo de ejecución que crece de manera gradual con el tamaño de la entrada, como en el caso de la búsqueda binaria, donde la complejidad temporal no se ve afectada en gran medida con el aumento del tamaño de la lista.

O(x): Tiempo lineal

Los algoritmos conO(x)representan una complejidad temporal lineal, es decir, el tiempo de ejecución crece proporcionalmente al tamaño de la entrada.

Un ejemplo sencillo en Python de un algoritmo con complejidad O(x)es un código que recorre una lista de nelementos y realiza una operación con cada uno de ellos. Por ejemplo, el siguiente código suma todos los elementos de una lista:

def sum_elements(list):
    sum = 0
    for i in list:
        sum += i
    return sum

array = [1,2,3,4,5,6,7,8,9,10]
total = sum_elements(array)

En este caso, el tiempo de ejecución del código depende directamente del tamaño de la lista (list), ya que se realiza una operación con cada elemento de la lista. Por lo tanto, el algoritmo tiene una complejidad O(n).

Es importante tener en cuenta que la complejidad temporal no solo depende del tamaño de la entrada, sino también de la cantidad de operaciones realizadas dentro del algoritmo. En este caso, como solo se realiza una operación (suma) con cada elemento de la lista, el algoritmo es lineal.

En resumen, ⁣O(x)representa una complejidad temporal lineal, es decir, el tiempo de ejecución aumenta proporcionalmente al tamaño de la entrada y en este ejemplo se evidencia como el bucle for recorre todos los elementos de la lista y realiza una operación con cada uno de ellos.

O(x log x): Complejidad logarítmica-lineal

Esta complejidad se da en algoritmos que tienen una complejidad logarítmica en una variable y una complejidad lineal en otra. Un ejemplo de esto es el algoritmo de ordenamiento Merge Sort, en el cual el tiempo de ejecución aumenta con el tamaño de la entrada y con la cantidad de operaciones de dividir y combinar las partes de la entrada.

def merge_sort(list):
    if len(list) <= 1:
        return list
    mid = len(list) // 2
    left = merge_sort(list[:mid])
    right = merge_sort(list[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

array = [5,3,8,1,9,7,6,10,2,4]
sorted = merge_sort(array)

En este caso, el algoritmo divide la lista en partes recursivamente hasta que cada parte contiene solo un elemento, y luego combina las partes ordenadas.

El proceso de dividir la lista en partes tiene una complejidad logarítmica en relación con el tamaño de la lista, mientras que el proceso de combinar las partes tiene una complejidad lineal en relación con el tamaño de la lista. Por lo tanto, el algoritmo tiene una complejidad O(x log x).

En resumen, O(x log x) representa una complejidad temporal logarítmica-lineal, es decir, el tiempo de ejecución aumenta con el tamaño de la entrada y con la cantidad de operaciones logarítmicas.

O( x² ): Tiempo cuadrático

Los algoritmos conO(x²)representa una complejidad temporal cuadrática, es decir, el tiempo de ejecución aumenta de manera proporcional al cuadrado del tamaño de la entrada.

Un ejemplo de esto es el algoritmo de ordenamiento Bubble sort. El siguiente código muestra una implementación sencilla de Bubble sort en Python:

def bubble_sort(list):
    n = len(list)
    for i in range(n):
        for j in range(0, n-i-1):
            if list[j] > list[j+1]:
                list[j], list[j+1] = list[j+1], list[j]
    return list

array = [5,3,8,1,9,7,6,10,2,4]
sorted_array = bubble_sort(array)
print(sorted_array)

En este caso, el algoritmo recorre la lista varias veces, comparando y cambiando de lugar elementos. El proceso de comparar y cambiar elementos se realiza en un ciclo dentro de otro ciclo (anidado) y el número de operaciones realizadas aumenta de manera exponencial en relación con el tamaño de la lista. Por lo tanto, el algoritmo tiene una complejidad O(x)².

En resumen, este algoritmo recorre un arreglo dos veces, por lo tanto, el tiempo de ejecución de este algoritmo es O(x²). Esto es porque el tiempo de ejecución aumenta cuadráticamente con el tamaño del arreglo. Si el tamaño del arreglo es 2, el algoritmo se ejecuta 4 veces; si el tamaño del arreglo es 5, el algoritmo se ejecuta 25 veces, y así sucesivamente.

O(2^x ): Tiempo exponencial

El término “O(2^x)” se refiere a una función de complejidad computacional de orden exponencial. Esto significa que el tiempo de ejecución de un algoritmo aumenta exponencialmente con respecto al aumento de los datos de entrada.

Un ejemplo sencillo en Python para una función de O(2^x) es la serie de Fibonacci. Esta serie de números se genera como sigue:

def fibonacci(n):
   if n<0:
      print("Incorrect input")
   # First Fibonacci number is 0
   elif n==1:
      return 0
   # Second Fibonacci number is 1
   elif n==2:
      return 1
   else:
      return fibonacci(n-1)+fibonacci(n-2)

print(fibonacci(10))

En resumen, esta función recursiva es O(2^x) porque cada vez que se llama a sí misma, la cantidad de cálculos aumenta exponencialmente. La razón de esto es que el tiempo de ejecución se vuelve cada vez más largo debido al número creciente de llamadas a la función Fibonacci(). Esto significa que con una entrada de n, hay 2^n llamadas a la función.

O(x! ): Tiempo Factorial

Una función con una complejidad de O( x! ) significa que la cantidad de tiempo que tarda en ejecutarse es equivalente a un factorial de x. Esto significa que el tiempo de ejecución aumenta exponencialmente con el aumento de la entrada.

Un ejemplo en Python para explicar esto es el siguiente:

def factorial(x):
   if x == 0:
      return 1
   return x * factorial(x - 1)

print(factorial(5))

En resumen, esta función toma un número x como parámetro y devuelve el resultado de la multiplicación de x por x — 1 por x — 2 por x — 3, etc. hasta llegar a 1. Esto significa que cuando x se incrementa en 1, el tiempo de ejecución se incrementa en un factor de x. Por lo tanto, la complejidad de esta función es O(x!).


✍️ Ejercicios

Bueno, ya hemos visto varios ejemplos de complejidades algorítmicas y para reforzar el aprendizaje, aquí te dejaré unos ejemplos sencillos para practicar lo aprendido 👹 je, je, je, pero no te preocupes, dejaré la respuesta al final del articulo para que puedas corroborar tu respuesta ánimo 💪😁.

def f(n):
   result = 0
   for i in range(n):
      result += i
   return result

n = 5
f(n)
def f(n)
  for i in range(n):
    for j in range(n):
      print(i, j)

n = [1,2,3,4,5,6,7,8,9]
f(n)
for i in range(n):
  for j in range(n):
    for k in range(n):
      print(i, j, k)

n = [1,2,3,4,5,6,7,8,9]
f(n)


😎 Conclusión

En conclusión, la notación Big O es una herramienta útil para evaluar la complejidad computacional de algoritmos. Esta herramienta nos permite medir el rendimiento de algoritmos y compararlos entre ellos. Esto nos ayuda a elegir el algoritmo más eficiente para una tarea determinada. Ademas del enorme valor que te aporta el conocerlo a tu carrera profecional 😉.

Espero haberte brindado información útil y relevante. Si has llegado hasta aquí, significa que estás interesado en la notación Big O, por lo que te animo a seguir investigando y aprendiendo más sobre este tema, sobre todo los temas de complejidad computacional y análisis de algoritmos 😎.

Si te ha gustado este artículo te agradecería enormemente unos generosos 👏 je, je, je. Además de dejarnos tus comentarios o preguntas en la sección de abajo, estaré encantado de responderte. ¡Hasta pronto!

via GIPHY

Respuestas

Ejercicio 1: O(x)

Ejercicio 2: O(x²)

Ejercicio 3: O(x^3)