El espacio auxiliar es el espacio ocupado menos el espacio ocupados por los datos de entrada
Fundamentos de Algoritmos
Todo lo que aprenderás sobre complejidad algorítmica con JS
Estructura de un algoritmo
¿Cómo elegir un buen algoritmo?
Complejidad algorítmica
Introducción a complejidad algorítmica
Complejidad espacial
Complejidad temporal
Complejidad temporal en práctica
Complejidad espacial en práctica
El estado de la complejidad
Análisis asintótico
Introducción a análisis asintótico
Notación Big-O
Cálculo de la notación Big-O
Evaluación de complejidad temporal con Big-O
Evaluación de complejidad espacial con Big-O Avanzado
Recomendaciones
Recomendaciones para la evaluación de algoritmos
Notas sobre algoritmos
Cierre del curso
Bonus
Determinando la complejidad un algoritmo avanzado
No tienes acceso a esta clase
¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera
Cuando existen varias sentencias, se escoge la notación mayor entre todas las existentes en el algoritmo.
Ahora que ya calculaste la complejidad temporal con Big-O, trata de calcular de la misma forma la complejidad espacial. Recuerda que el espacio auxiliar es la memoria almacenada sin tener en cuenta los datos de entrada.
El siguiente algoritmo de búsqueda contiene dos notaciones Big-O. La notación contante corresponde a la variable indice
generada. La notación lineal correspondiente al arreglo
en los datos de entrada.
function linearSearch(arreglo, clave) { // O(n)
for (let indice = 0; indice < arreglo.length; indice++) { // O(1)
if (arreglo[indice] === clave) { // No se genera espacio en memoria
return indice; // No se genera espacio en memoria
}
}
return -1; // No se genera espacio en memoria
}
Por lo tanto, la complejidad del algoritmo estará determinada por la complejidad mayor que exista. En este caso constante O(n)
, y el espacio auxiliar tendrá una complejidad constante O(1)
.
/**
* Complejidad Espacial -> O(n)
* Espacio Auxiliar -> O(1)
*/
El siguiente algoritmo de búsqueda contiene una notación Big-O. La notación contante corresponde a las variables generadas dentro de la función. La notación lineal correspondiente al arreglo
en los datos de entrada.
function bubbleSort(arreglo) {
let longitud = arreglo.length; // O(1)
for (let i = 0; i < longitud; i++) { // O(1)
for (let j = 0; j < longitud; j++) { // O(1)
if (arreglo[j] > arreglo[j + 1]) { // No se genera espacio en memoria
let temporal = arreglo[j]; // O(1)
arreglo[j] = arreglo[j + 1]; // No se genera espacio en memoria
arreglo[j + 1] = temporal; // No se genera espacio en memoria
}
}
}
return arreglo; // No se genera espacio en memoria
}
Por lo tanto, la complejidad del algoritmo estará determinada por la complejidad mayor que exista. En este caso constante O(n)
, y el espacio auxiliar tendrá una complejidad constante O(1)
.
/**
* Complejidad Espacial -> O(n)
* Espacio Auxiliar -> O(1)
*/
El siguiente algoritmo de búsqueda contiene una notación Big-O. La notación contante corresponde a las variables generadas dentro de la función. La notación lineal correspondiente al arreglo
en los datos de entrada.
function selectionSort(arreglo) {
let longitud = arreglo.length; // O(1)
for (let i = 0; i < longitud; i++) { // O(1)
let minimo = i; // O(1)
for (let j = i + 1; j < longitud; j++) { // O(1)
if (arreglo[j] < arreglo[minimo]) { // No se genera espacio en memoria
minimo = j; // No se genera espacio en memoria
}
}
if (minimo != i) { // No se genera espacio en memoria
let temporal = arreglo[i]; // O(1)
arreglo[i] = arreglo[minimo]; // No se genera espacio en memoria
arreglo[minimo] = temporal; // No se genera espacio en memoria
}
}
return arreglo; // No se genera espacio en memoria
}
Por lo tanto, la complejidad del algoritmo estará determinada por la complejidad mayor que exista. En este caso constante O(n)
, y el espacio auxiliar tendrá una complejidad constante O(1)
.
/**
* Complejidad Espacial -> O(n)
* Espacio Auxiliar -> O(1)
*/
Contribución creada por Andrés Guano (Platzi Contributor).
Aportes 18
Preguntas 4
El espacio auxiliar es el espacio ocupado menos el espacio ocupados por los datos de entrada
Yo pensando que sacar la Big-O de un algoritmoiba a ser mucho más complejo y resultó ser bastante divertido y sencillo
Muy buenas explicaciones
En este momento todas las piezas terminaron de calzar, esta muy cool el curso 😄
El espacio auxiliar es el espacio ocupado menos el espacio ocupados por los datos de entrada
Muy buena explicación 😃
Esto esta genial ya entendí qué onda con las opciones que se salta, ya pude armar el rompecabezas de todo este conocimiento wow
Excelente docente!!!
Freddy, atentti!!!
Aqui hay otro Diego Granda!!!
Excelente explicación 👄
Vengo mucho tiempo tratando de entender big o, y contigo lo he logrado entender, muchas gracias!
Yo durante todo el curso
por fin pude entender todo 😃
¡Excelente explicación profe Marcelo! 👏🏽👏🏽👏🏽
Waaaao que buena explicacion gracias bro
muy buena clase!
¿Quieres ver más aportes, preguntas y respuestas de la comunidad?