Notación Big O

Como no veo este curso en los Recursos les dejo este curso que me ayudo a comprender Big O de una manera facil y rapida https://platzi.com/cursos/complejidad-js/

Les comparto un video en inglés, bastante comprensible explicando el tema de complejidad computacional:

www .youtube. com/watch?v=47GRtdHOKMg

• Constant - O(1)
  Runtime does not depend on input size
  Example: Look up the first item
  [1,2,5]

• Logarithmic - O(log(n))
  Runtime grows slower than the input size
  Example: Binary Search
  Search an element in an ordered list
  Open dictionary in half
  Check value
  See if is at the first half or the second half of the dictionary

• Linear - O(n)
  The runtime grows at the same rate as the input.
  Example: Unsorted list

• Log-Linear - O(n log(n))
  An operation of log(n) complexity for each input value
  Example: Efficient Sorting

• Quadratic - O(n^2)
  An operation of complexity O(n) is carried out for each input
  Example: Check all pairs of input values (Double for loop)

• Polynomial - O(n^3)…
  Computations with other exponents (n^4, n^5, etc)
  Example: Check all triplets of input values (Triple for loop)

• Exponential - O(2^n)…
  Complexity is multiplied (doubled, tripled, etc) with each additional input value
  Example: Recursive Algorithms - Traveling salesman problem

• Worse- O(n!)
  Runtimes can be worse than exponential
  Examples: Permutations

Le pregunté a chatgpt que me explicara el concepto de Notación Big o para un niño de 10 años y esto me dijo:

¡Claro! Voy a intentar explicar la notación Big O de una manera sencilla para un niño de 10 años.

La notación Big O se usa en programación para describir la eficiencia de un algoritmo. Imagina que tienes que ordenar una lista de números en orden ascendente. Hay diferentes formas de hacer esto, algunas más rápidas que otras. Si usas un algoritmo muy lento, puede que tardes mucho tiempo en ordenar la lista, especialmente si la lista es muy grande.

La notación Big O se utiliza para medir cuánto tiempo tarda un algoritmo en completarse en función del tamaño de los datos de entrada. En otras palabras, mide la rapidez con la que un algoritmo puede procesar datos a medida que la cantidad de datos aumenta.

Por ejemplo, si tienes que ordenar una lista de 10 elementos, es posible que un algoritmo tardara unos segundos en completar la tarea. Pero si tienes que ordenar una lista de 1 millón de elementos, el mismo algoritmo podría tardar varios minutos o incluso horas.

La notación Big O se representa con una letra “O” seguida de una función matemática que describe la eficiencia del algoritmo en función del tamaño de los datos de entrada. Por ejemplo, si un algoritmo tarda un tiempo constante en completarse, se escribiría como O(1). Si el tiempo que tarda el algoritmo aumenta linealmente con el tamaño de los datos de entrada, se escribiría como O(n), donde “n” es el tamaño de los datos de entrada.

En resumen, la notación Big O es una manera de medir la eficiencia de un algoritmo en función del tamaño de los datos de entrada. Si un algoritmo tiene una notación Big O pequeña, significa que es muy eficiente y puede procesar grandes cantidades de datos rápidamente. Si el algoritmo tiene una notación Big O grande, puede tardar mucho tiempo en procesar grandes cantidades de datos.

creo que lo correcto habría sido decir que las complejidades son O(log x), O(x) porque el eje es x, la otra opción es cambiar x por n para ilustrar mejor la relación entre el aumento de valores con su función

La notación Big O es una forma de medir la complejidad de un algoritmo. Se utiliza para determinar cuánto tiempo y espacio se tarda un algoritmo en ejecutarse.

La notación Big O se representa como O(n), donde n es el tamaño del conjunto de datos de entrada. Esto significa que la complejidad del algoritmo aumenta proporcionalmente al tamaño del conjunto de datos.

Por ejemplo, si tenemos un algoritmo que tarda 1 segundo en procesar un conjunto de datos de tamaño 100, y tarda 2 segundos en procesar un conjunto de datos de tamaño 200, podemos decir que la complejidad del algoritmo es O(n), ya que el tiempo de ejecución se duplica cuando el tamaño del conjunto de datos se duplica.

La notación Big O se utiliza para analizar la eficiencia de los algoritmos y para comparar diferentes algoritmos entre sí. Es importante encontrar el algoritmo más eficiente para resolver un problema determinado, ya que esto puede marcar una gran diferencia en el rendimiento de una aplicación.

En resumen, la notación Big O es una herramienta útil para evaluar la complejidad de los algoritmos y encontrar el más eficiente para resolver un problema determinado.

Chio Code - Notacion Big O https://www.youtube.com/watch?v=MyAiCtuhiqQ&ab_channel=ChioCode

Esta clase me gustó mucho y me parece una explicación sencilla para entender el concepto pero sin duda se debe profundizar. Les comparto un pequeño post donde hablan un poco más de estas notaciones tan importantes.

• https://medium.com/nowports-tech/introducción-a-big-o-notation-95ecca8bd866

Me pareció muy buena explicación. Lo que debe ser y sencillo.