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 18

Preguntas 4

Ordenar por:

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

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

<u>El espacio auxiliar</u> `Complejidad espacial - Espacio de entrada = O( n ) - O( 1 ) —simplificamos—> O( 1 )`

Excelente explicación 👄

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

Existe una Forma Muy Practica de Mejorar / Optimizar el BubbleSort Algorithm y es agregando una Var AUX : int flg = 0 ; entre el Outer\_For y el Inner\_For para ver si el Algoritmo hizo algun cambio en el Array o Not, esta Flag sera una variable Aux extra, si se creasee otra variable : size = array.Length , para luego recorrer Los Forx2 sera otra vairable aux por l oque ya serian tres variables aux \[ i, flg, size ] a lo que es O ( 3 ) --> O ( 1 ) para Aux\_Space. \n

Yo durante todo el curso

por fin pude entender todo 😃

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

Waaaao que buena explicacion gracias bro

muy buena clase!

El big o del for esta mal explicado, ya que ademas de la asignacion inicial, durante la ejecucion del mismo, se comprueba la condicion y incrementa (asigna y suma) en la variable utilizada por lo que es O(3n) de un for. Comprendo que se simplifique a O(1) con fines pedagogicos sin embargo no viene mal aclararlo o comentarlo durante el curso.