Aún no tienes acceso a esta clase

Crea una cuenta y continúa viendo este curso

Evaluación de complejidad temporal con Big-O

13/18
Recursos

Aportes 10

Preguntas 4

Ordenar por:

¿Quieres ver más aportes, preguntas y respuestas de la comunidad? Crea una cuenta o inicia sesión.

📂 Genial, ahora puedes practicar con más algoritmos desde la carpeta algorithms del repositorio del curso.

🙏 Te invito a hacerlo, pues con esto empleas las reglas para hallar la notación Big-O de varios algoritmos que podrás emplear en entrevistas técnicas.

Solo como pequeña nota que no cambia el los resultados.
Estrictamente hablando. Hay algunos procesos que no se suman ya que están dentro de un for por lo tanto no se ejecutan una unica vez, se ejecutan por cada iteración
.


Buble Sort

  • 1 + n( n(1 + 1 + 1 + 1) ) + 1
  • n(4n) + 2
  • 4n^2 + 2
  • O(n^2) // Solo se toma el exponente mas grande
    .

Selection Sort

  • 1 + n( 1 + n(1 + 1) + 1 + 1 + 1 + 1 ) + 1
  • n( 2n + 5 ) + 2
  • 2n^2 + 5n + 2
  • O(n^2) // Solo se toma el exponente mas grande
    .

Al fin entiendo el ordenamiento por burbuja!
Además de aprender del ordenamiento lineal y de selección 😄

Forma de analizar la notación big-o en complegidad temporal

Constantes, variables y condicionales

const entrada = input(); // O(1)
const x = 5; // O(1)
if entrada == "holi" { // O(1)
    print("saludo" * x) // O(1)
}

Ciclos o iteraciones

// Donde "n" es la entrada y "c" es una constante
for (let i = 1; i <= n; i += c) { // O(n)
    // Cualquier sentencia O(1)
}

for (let i = n; i > 0; i -= c) { // O(n)
    // Cualquier sentencia O(1)
}

Ciclos anidados

// Donde "n" es la entrada y "c" es una constante
for (let i = 1; i <= n; i += c) {
    for (let j = 1; j <= n; j += c) { // O(n²)
        // Cualquier sentencia O(1)
    }
}

for (let i = n; i > 0; i -= c) {
    for (let j = 1; j <= n; j += c) { // O(n²)
        // Cualquier sentencia O(1)
    }
}

Ciclos con incremento extenso

// Donde "n" es la entrada y "c" es una constante
for (let i = 1; i <= n; i *= c) { // O(log[n])
    // Cualquier sentencia O(1)
}

for (let i = n; i > 0; i /= c) { // O(log[n])
    // Cualquier sentencia O(1)
}

Ciclos con incremento exponencial

// Donde "n" es la entrada y "c" es una constante
for (let i = 2; i <= n; i = pow(i, c)) { // O(log[log[n]])
    // Cualquier sentencia O(1)
}

for (let i = n; i > 1; i = func(i)) { // O(log[log[n]])
    // Cualquier sentencia O(1)
}

Vale, entonces no es tanto la cantidad de pasos que se toman, es decir si afectan por supuesto, pero no es la forma en que calificaríamos un algoritmo respecto su desenpeño.
_
Sino que esta relacionado a la repeticion y lo anidados que los pasos del algoritmo segun el tamaño de el input.

Les dejo este enlace para revisar cómo la complejidad llega a casos como logaritmos o factoriales.
https://careerkarma.com/blog/big-o-notation-time/

Ojo, un bloque de tipo bucle dentro de otro bloque es una multiplicación, y bloques diferentes es una adición! O(n *1 *1 + 1) -> O(n)

Comparto otra manera de implementar búsqueda lineal, con un solo return, haciendo el código más legible como una buena práctica de código limpio:
.

function linealSearch(arr, value) {
    let found = false;
    let key = -1;
    let index = 0;
    while(index = 0 < arr.length && found == false) {
        if(arr[index] == value) {
            found = true;
            key = index;
        }
        index++;
    }
    return key;
}

yo tampoco creo que todo sea tan fácil, estoy seguro que hay matemáticas complejas en todo esto donde se podrán hacer demostraciones de que esa Big-O tiene esa complejidad, aun así estoy aprendiendo mucho.

Creo que usando ciclos for e if statements es buena idea para poder evaluar lo complejidad de cada uno de los algoritmos. Sin embargo, se pueden hacer mucho mas cortos con algunos de los métodos que JS nos ofrece por defecto.
.
Ejemplo con el algoritmo de linearSearch

function linearSearch(arr, value){
  return arr.find(item => item === value)
}

const arr = [1,2,3,4,5,6,7,8,9,10];
console.log( linearSearch(arr, 8) ) // 8