No tienes acceso a esta clase

隆Contin煤a aprendiendo! 脷nete y comienza a potenciar tu carrera

Notaci贸n Big-O

11/18
Recursos

Con la notaci贸n Big-O buscamos descubrir una funci贸n (constante, lineal, polinomial, logar铆tmica y exponencial) que sea mayor o igual que la complejidad de un algoritmo, es decir, el peor caso que puede ejecutarse el programa.

Clases de Big-O

Las clases de Big-O son las representaciones simb贸licas del tipo de crecimiento del algoritmo en el peor de los casos. El tipo de crecimiento es la funci贸n que se aproxima a los resultados de los valores de tiempo o espacio.

Esta representaci贸n simb贸lica consiste en la letra O may煤scula seguida de par茅ntesis que incluyen el tipo de crecimiento.

Clases de la notaci贸n Big-O

De esta manera, ya conoces las funciones representadas en la siguiente gr谩fica, donde las peores complejidades est谩n situadas al extremo superior izquierdo, y las mejores est谩n en el extremo inferior derecho. De las cuales representan el rendimiento del algoritmo.

Gr谩ficas representativas de la complejidad

Fuente: Big-O Cheat Sheet

Contribuci贸n creada por Andr茅s Guano (Platzi Contributor).

Aportes 14

Preguntas 2

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad?

o inicia sesi贸n.

鈽 Somos seres precavidos. Cuando asistimos a un viaje, podemos llevar m谩s dinero de la cuenta. Por si algo sucede mal.
Resultado de esto:

驴$150? Mejor que sean $200.

鉂 Hay muchas otras notaciones, pero lo que hace a Big-O tan importante es que se destaca en concentrarse en el caso peor de tu algoritmo.
馃敐 En el tope superior de nuestras mediciones. Si nuestro algoritmo empez贸 con unas mediciones muy buenas, pero de pronto creci贸 mucho en el consumo de un recurso. Big-O tomar谩 en cuenta esto 煤ltimo para determinar qu茅 crecimiento le pertenece.
Resultado de esto:

驴Crecimiento constante? Mejor que sea crecimiento lineal.

Big-O no contar谩 tanto con las mediciones peque帽as, sino con las mediciones grandes.


馃憗鈥嶐煑 Mira esta animaci贸n, y f铆jate c贸mo el cambiar los puntos superiores determina d贸nde se traza la l铆nea, que nos indica un O(n).

驴Porque necesitamos una notaci贸n?
La queremos usar para poder simplificar el an谩lisis de la complejidad computacional

buscamos poder simplificar la representaci贸n de la complejidad

驴Qu茅 buscamos con Big-O?
Buscamos descubrir una funci贸n (constante, lineal, polinomial, logar铆tmica o exponencial) que sea mayor o igual que la complejidad de un algoritmo.

Clases de Big-O

Clase Crecimiento Formula Emoji
O(1) Constante $f(x) = 1 $ 馃槉
O(log(n)) Logar铆tmico $f(x) = \log_{10}(x) $ 馃檪
O(n) Lineal $f(x) = x $ 馃樁
O($n^2$) Cuadr谩tico $f(x) = x^2 $ 馃檨
O($2^n$) Exponencial $f(x) = 2^x $ 馃槩
O(n!) Factorial $f(x) = x! $ 馃槶

Formulas de cada una las clases de complejidades:

  • Cuadratico:
 f(x)=x^(2)
  • Lineal:
 g(x)=x
  • Constante:
 b(x)=1
  • Exponencial:
 c(x)=2^(x)
  • Logaritmico:
 l(x)=log(10,x)
  • Factorial:
 t(x)=x!
  • O(1) = O(鈽猴笍)

  • O(log n) = O(馃檪)

  • O(n) = O(馃樁)

  • O(n^2) = O(馃檨)

  • O(2^n) = O(馃槩)

  • O(n!) = O(馃槶)

Les dejo el link con el ejercicio en GeoGebra

https://www.geogebra.org/calculator/wc7dgmbt

Marcelo esa expresi贸n 鈥渁mbos dos鈥 que mucho la utilizas ha ca铆do en desuso en el espa帽ol, no se si tu lengua nativa es el ingl茅s y por eso la usas tan frecuentemente, te dejo un enlace a la RAE

https://www.rae.es/dpd/ambas

馃挘 Notaci贸n Big-O

Apuntes

  • La notaci贸n cient铆fica nos ayuda para acortarlos, con notaci贸n Big O se desea realizar eso

驴Por qu茅 necesitamos una notaci贸n?

  • Una notaci贸n es necesaria para simplificar la complejidad, evitando variar con mediciones o gr谩ficas

驴Qu茅 buscamos con Big-O?

  • Buscamos descubrir una funci贸n (Constante, Lineal, Polinomial, Logar铆tmica, Exponencial) la cual sea mayor o igual que la complejidad de un algoritmo
Clase Crecimiento
O(1) Constante
O(log n) Logar铆tmico
O(n) Lineal
O(n虏) Cuadr谩tico
O(2^n) Exponencial
O(n!) Factorial
  • Si bien las clases parecen funciones son solo clases
  • Clases significa una forma de llamar
    • Constante 鈬 O(1)
Clase Emoji
O(1) O(馃槉)
O(log n) O(馃檪)
O(n) O(馃樁)
O(n虏) O(鈽癸笍)
O(2^n) O(馃槩)
O(n!) O(馃槶)

Este enlace de los recursos ya no sirve 馃様:
https://radiant-anchorage-11930.herokuapp.com/

Un ejemplo de logaritmo es cuando compilas de tal manera y con la cantidad adecuada de input que ahorras segundos, estos segundos con el tiempo es eso tiempo ganado o menos gasto de recursos, que al principio parece no importar mucho pero cada segundo por cada calculo o comunicaci贸n va acumul谩ndose en el tiempo.

La notacion Big-O es una espcie de imagen o de nivel de los algoritmo

no entendi naaaaaaaa

馃槙

La notaci贸n Big-O es una forma com煤nmente utilizada en el an谩lisis asint贸tico para describir el rendimiento de un algoritmo. Se utiliza para indicar el l铆mite superior del tiempo de ejecuci贸n de un algoritmo a medida que el tama帽o de los datos aumenta.

Por ejemplo, si un algoritmo tiene una complejidad de O(n^2), significa que el tiempo de ejecuci贸n del algoritmo aumenta cuadr谩ticamente con el tama帽o de los datos. Esto significa que si el tama帽o de los datos se duplica, el tiempo de ejecuci贸n aumentar谩 por un factor de cuatro.

La notaci贸n Big-O se utiliza a menudo para describir el rendimiento de algoritmos en t茅rminos de su orden de crecimiento. Otros t茅rminos comunes incluyen la notaci贸n Big-惟 (omega) y Big-螛 (theta). Big-惟 describe el l铆mite inferior del rendimiento de un algoritmo, mientras que Big-螛 describe el rendimiento exacto de un algoritmo.

Notaci贸n Big-O

La notaci贸n Big O se utiliza para analizar el rendimiento de un聽algoritmo, lo cual es una forma matem谩tica b谩sica de expresar cuanto tarda un algoritmo en ejecutarse atendiendo s贸lo a grandes rasgos su eficiencia y as铆 poder compararlo con otros. En definitiva evaluar su complejidad y poner nota a su eficiencia.

As铆 como utilizamos la notaci贸n cient铆fica para escribir n煤meros muy grandes o muy peque帽os,

驴Por qu茅 necesitamos una notaci贸n?

Una notaci贸n es necesaria para simplificar la complejidad y para evitar variaciones.

驴Qu茅 buscamos con Big-O?

Descubrir una funci贸n (constante, lineal, polinomial, logar铆tmica, y exponencial) que sea mayor o igual que la complejidad de un algoritmo.

Clases de Big-O

Clase Crecimiento F贸rmula Emoji
O(1) Constante b(x)=1 馃槉
O(log n) Logar铆tmico l(x)=log(10,x) 馃檪
O(n) Lineal g(x)=x 馃樁
O(n虏) Cuadr谩tico f(x)=x^(2) 鈽癸笍
O(2鈦) Exponencial c(x)=2^(x) 馃槩
0(n!) Factorial t(x)=x! 馃槶