Notación Big O

Clase 7 de 11 • Curso de Entrevistas Técnicas: Estructuras de Datos y Algoritmos Avanzados

Alen Samuel

student•

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/

Camila Londoño

teacher•

Gracias por compartir

Rigel David Gutiérrez Carbajal

student•

También se encuentra para python :D

Jackeline Puruaya

student•

Andres Silva Vega

student•

Miguel Negron Garcia

student•

Para aquellos que usan Chat GPT para estudiar"

Para que le explique el tema que no dominan o que quieren que este mas claro pidanle que les explique el tema usando la tecnica Feyman, si quieren que le haga preguntas para ver cuanto comprendieron del tema pues que use la tecnica Socratica.

Lo uso todo el tiempo y me ha ayudado mucho. Suerte a todos.

Frandel Corporan Rodríguez

student•

Gracias bro!

Tomás Carrión

student•

Game-changing. Gracias

Luis Fernando Forero Guzmán

student•

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

Walter De Jesús Medina Puy

student•

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

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

Julian David Alzate Cuervo

student•

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.

Javier Amador Amador

student•

Genial explicaion, muchas gracias por tu aporte amigo

Frandel Corporan Rodríguez

student•

Con esto lo entendí mucho mejor

Alfredo Olmedo

student•

Notación Big O

Juan Manuel Nava Zamudio

student•

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

GIANKARLO ROJAS

student•

Puedes revisar este curso https://platzi.com/cursos/complejidad-js/ para aclarar dudas

Ramses Acosta

student•

Complejidad constante “Así aumenten la cantidad de datos que entran, no aumenta ya sea el tiempo, la memoria” esto a mi me resulta muy confuso, porque si tu aumentas el numero de datos para procesar si o si va aumentar el tiempo o los recursos a usar, si tienes que procesar 10 datos no va a ser lo mismo que procesar 1000, se necesitan mas ciclos de reloj del procesador al igual que si asignamos una (1) variable no es lo mismo que asignar 1000.

Juan Castro

teacher•

Imagina este caso:

function (array) {
  return array[0];
}

No importa si el array tiene 10 elementos o 500 mil, lo único que hace nuestra función es retornar el primero, así que la complejidad no aumenta con el número de elementos del array.

Por supuesto que crear una variable con 10 o 500 mil elementos es muy distinto. Pero recuerda que al calcular la complejidad de nuestros algoritmos tenemos en cuenta lo que hacemos durante el algoritmo (por decirlo así, dentro de la función, no por fuera).

Si nuestra función crea una nueva variable por cada elemento del array que recibe como parámetro, entonces la complejidad espacial aumenta también, pero si nuestra función "solo" recibe el array pero no crea nuevas variables que dependan de esa cantidad de elementos, entonces no aumenta esa complejidad.

Ramses Acosta

student•

parcero mil gracias, tu ejemplo es muy claro, lo que estuve pensando es que deberíamos de contar ciclos reloj mira pensé en hacer un convert con algo asi psudo codigo a assembler y ahí si se puede ver de mejor manera como es la complejidad. pero muy buen ejemplo me ayudo a entender mejor el concepto.

Daniel Buitrago

student•

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%C3%B3n-a-big-o-notation-95ecca8bd866

Ivan Camilo Buitrago Buitrago

student•

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.

Pablo Torres Pérez

student•

Les dejo una hoja de trucos (Cheat Sheet) con operaciones comunes en diferentes estructuras de datos y la complejidad de cada una. Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell

Francisco Fabian Montaño López

student•

La notación Big O es una forma de describir la complejidad algorítmica de un algoritmo en términos de tiempo o espacio en función del tamaño de la entrada. Se utiliza para clasificar algoritmos según su rendimiento en el peor de los casos, permitiendo comparar la eficiencia de diferentes algoritmos. Por ejemplo, O(n) indica que el tiempo de ejecución crece linealmente con el tamaño de la entrada, mientras que O(n^2) sugiere un crecimiento cuadrático. Conocer esta notación es fundamental para optimizar la programación y prepararse para entrevistas técnicas.

Andres Silva Vega

student•

Miguel Angel Reyes Moreno

student•

Les comparto 2 vídeos que explican la Big O Notation: - [Big-O Notation in 100 Seconds](https://www.youtube.com/watch?v=g2o22C3CRfU) - [Time Complexity | Big O Notation | Data Structures & Algorithms | JomaClass](https://www.youtube.com/watch?v=v1SYihb4rcw)