Cálculo de la notación Big-O

let bar = 'test'	// O(1)
if() {}		// O(1)
for() {}		// O(n)
while() {}	// O(n)
for() { for() {} }// O(n^2)

Me está encantando el curso 😄, les comparto mis apuntes de esta clase:

Notación Big-O en complejidad temporal

let bar = 'test'	// O(1)
if() {}		// O(1)
for() {}		// O(n)
while() {}	// O(n)
for() { for() {} }// O(n^2)

Big-O complejidad algoritmica espacial

let bar = 'test'  // 0(1)
if () {}               // 0(1)
for () {}             // 0(1)
let resultado = [1,2,...,n]  // 0(n)
let dimensional = [[2,4],[6,8],[10,12]] //0(n^2)

El crecimiento importa

La complejidad de un algoritmo nace de cuántos recursos utiliza el algoritmo al ejecutarse.

La notacion Big-O solo se enfoca en el crecimiento.

Un algoritmo puede correr en una computadora muy vieja-lenta o en una muy nueva-rapida, pero el crecimiento (ritmo) sea el mismo, la complejidad será la misma. Pero esto es en base a los recursos que esa computadora tiene.

Conclusión

Revisamos el código en nuestro algoritmo para medir su complejidad en la notación Big-O.

La notacion Big-O se enfoca en el crecimiento

🗳️ Cálculo de la notación Big-O

Apuntes

• Para poder calcular la notación Big O depende si se desea medir el tiempo o espacio

Notación Big-O en complejidad temporal

let bar = 'test' // O(1)
if(){} // O(1)
for(){} // O(n)
while(){} // O(n)
for(){ for(){} } // O(n^2)

Notación Big-O en complejidad espacial

• Comprende en ver cuantas variables se van creando

let bar = 'test' // O(1)
if(){} // O(1)
for(){} // O(1)
let resultado = [1, 2, ..., n] // O(n)
let dimensional = [[1, 2], [3, 4], ...] // O(n²)

• Para simplificar la notación nos concentramos en el valor podemos abreviarlo de la siguiente manera
  • O(2n) ⇒ O(n)
  • O(50) ⇒ O(1)
  • O(n² + 50) ⇒ O(n²)
• Es posible simplificar de esta manera, ya que solo nos importa el grado mayor

El crecimiento importa

• La complejidad de un algoritmo nace de cuantos recursos utiliza el algoritmo al ejecutarse.
• La notación Big-O solo se enfoca en el crecimiento.

Y en qué nivel de big-o queda una función recursiva? O(2^n)?

Cálculo de la notación Big-O

Notación Big-O en complejidad temporal

let bar = 'test'	// O(1)
if() {}		// O(1)
for() {}		// O(n)
while() {}	// O(n)
for() { for() {} }// O(n^2)

Big-O complejidad algorítmica espacial

let bar = 'test'  // 0(1)
if () {}               // 0(1)
for () {}             // 0(1)
let resultado = [1,2,...,n]  // 0(n)
let dimensional = [[2,4],[6,8],[10,12]] //0(n^2)

Para simplificar la notación quitamos los valores variantes no tan importantes, por ejemplo; con el número pi = 3.14159265358979, mientras más dígitos mayor precisos serán los resultados, pero ya que en los algoritmos el tiempo de ejecución siempre cambiará es mejor eliminar estas variaciones, quedándonos sólo con las clases, de la siguiente manera.

O(2n) ⇒ O(n)

O(50) ⇒ O(1)

O(n² + 50) ⇒ O(n²)

El crecimiento importa

La complejidad de un algoritmo nace de cuántos recursos utiliza el algoritmo al ejecutarse.

Así como un algoritmo se puede tardar más o menos dependiendo de factores como la computadora, memoria, etc. La complejidad de un algoritmo será siempre la misma, aunque en un dispositivo tarde 10 segundos y en otro 10 milisegundos, el ritmo de crecimiento se conserva.

Es por esto que la notación Big-O solo se enfoca en el crecimiento, y no en datos absolutos.

¿ De qué depende la optimización en ambas complejidades algorítmicas tanto temporal o espacial?

Big-O complejidad algoritmica espacial

let bar = 'test'  // 0(1)
if () {}               // 0(1)
for () {}             // 0(1)
let resultado = [1,2,...,n]  // 0(n)
let dimensional = [[2,4],[6,8],[10,12]] //0(n^2)

La notación Big-O consiste en encontrar la función que describe el crecimiento en el uso de recursos (tiempo o espacio), de allí que lo importante sea únicamente la función, no su desplazamiento a través del eje (que serian los términos independientes como “2” multiplicando o “50” sumando).