No tienes acceso a esta clase

¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera

Evaluación de complejidad espacial con Big-O Avanzado

14/18
Recursos

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.

Búsqueda lineal

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)
 */

Ordenamiento de burbuja

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)
 */

Ordenamiento de selección

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 14

Preguntas 4

Ordenar por:

¿Quieres ver más aportes, preguntas y respuestas de la comunidad?

o inicia sesión.

El espacio auxiliar es el espacio ocupado menos el espacio ocupados por los datos de entrada

Muy buenas explicaciones

En este momento todas las piezas terminaron de calzar, esta muy cool el curso 😄

Yo pensando que sacar la Big-O de un algoritmoiba a ser mucho más complejo y resultó ser bastante divertido y sencillo

El espacio auxiliar es el espacio ocupado menos el espacio ocupados por los datos de entrada

Muy buena explicación 😃

Excelente 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!!!

Vengo mucho tiempo tratando de entender big o, y contigo lo he logrado entender, muchas gracias!

por fin pude entender todo 😃

¡Excelente explicación profe Marcelo! 👏🏽👏🏽👏🏽

Waaaao que buena explicacion gracias bro

muy buena clase!