Skip to main content
Un moderador ha trasladado los comentarios al chat
Publicación recuperada por gbianchi
El moderador convierte en comentario
Publicación eliminada por gbianchi
se añadieron 195 caracteres en el cuerpo
Origen Enlace
Yussef
  • 23.4k
  • 4
  • 12
  • 29

De los comentarios asumo que estamos hablando solo de la complejidad temporal y dado que para este caso hablar de la complejidad espacial tiene poco sentido, atenderé solo a lo primero.

Si tienes una función:

function calcular(n) {
  n*=n
  for(let i=0; i<=n; i++){
    algo();
  }
}

Y digamos que calcular algo() demora siempre 1 segundo, con:

n Tiempo (s)
0 0
1 1
2 4
3 9
4 16

Como se puede ver el tiempo necesario (o la cantidad de operaciones), aumenta de forma cuadrática en relación a la entrada n, por tanto esa función es de

O(n2)


La complejidad no viene dada por la cantidad de for que tenga un algoritmo, si no que por la variación de la cantidad de operaciones que realiza en relación a la entrada n

La misma función se podría escribir como

function calcular(n) {
  for(let i=0; i<n; i++){
    for(let j=0;j<n;j++){
      algo();
    }
  }
  algo();
}

Y ahí estarían los 2 for, pero esa reescritura con cambia la complejidad, la función algo() con igual entrada n se ejecuta la misma cantidad de veces en ambos casos ¿por qué deberían tener complejidades algorítmicas distintas? No tendría lógica alguna.

Y lo mismo aplica en el caso contrario, digamos que tenemos esta función

function calcular(n) {
  for(let i=0; i<n; i++){
    algo();
  }
}

Es evidente que es de O(n), y si yo la reescribo de esta manera:

function calcular(n) {
  let n1 = Math.ceil(Math.sqrt(n));
  let n2 = n-n1;
  for(let i=0; i <n1; i++){
    for(let j=0; j<n2; j++){
      algo();
    }
  }
}

Sigue siendo de O(n) aunque tenga 2 for

Si tienes una función:

function calcular(n) {
  n*=n
  for(let i=0; i<=n; i++){
    algo();
  }
}

Y digamos que calcular algo() demora siempre 1 segundo, con:

n Tiempo (s)
0 0
1 1
2 4
3 9
4 16

Como se puede ver el tiempo necesario (o la cantidad de operaciones), aumenta de forma cuadrática en relación a la entrada n, por tanto esa función es de

O(n2)


La complejidad no viene dada por la cantidad de for que tenga un algoritmo, si no que por la variación de la cantidad de operaciones que realiza en relación a la entrada n

La misma función se podría escribir como

function calcular(n) {
  for(let i=0; i<n; i++){
    for(let j=0;j<n;j++){
      algo();
    }
  }
  algo();
}

Y ahí estarían los 2 for, pero esa reescritura con cambia la complejidad, la función algo() con igual entrada n se ejecuta la misma cantidad de veces en ambos casos ¿por qué deberían tener complejidades algorítmicas distintas? No tendría lógica alguna.

Y lo mismo aplica en el caso contrario, digamos que tenemos esta función

function calcular(n) {
  for(let i=0; i<n; i++){
    algo();
  }
}

Es evidente que es de O(n), y si yo la reescribo de esta manera:

function calcular(n) {
  let n1 = Math.ceil(Math.sqrt(n));
  let n2 = n-n1;
  for(let i=0; i <n1; i++){
    for(let j=0; j<n2; j++){
      algo();
    }
  }
}

Sigue siendo de O(n) aunque tenga 2 for

De los comentarios asumo que estamos hablando solo de la complejidad temporal y dado que para este caso hablar de la complejidad espacial tiene poco sentido, atenderé solo a lo primero.

Si tienes una función:

function calcular(n) {
  n*=n
  for(let i=0; i<=n; i++){
    algo();
  }
}

Y digamos que calcular algo() demora siempre 1 segundo, con:

n Tiempo (s)
0 0
1 1
2 4
3 9
4 16

Como se puede ver el tiempo necesario (o la cantidad de operaciones), aumenta de forma cuadrática en relación a la entrada n, por tanto esa función es de

O(n2)


La complejidad no viene dada por la cantidad de for que tenga un algoritmo, si no que por la variación de la cantidad de operaciones que realiza en relación a la entrada n

La misma función se podría escribir como

function calcular(n) {
  for(let i=0; i<n; i++){
    for(let j=0;j<n;j++){
      algo();
    }
  }
  algo();
}

Y ahí estarían los 2 for, pero esa reescritura con cambia la complejidad, la función algo() con igual entrada n se ejecuta la misma cantidad de veces en ambos casos ¿por qué deberían tener complejidades algorítmicas distintas? No tendría lógica alguna.

Y lo mismo aplica en el caso contrario, digamos que tenemos esta función

function calcular(n) {
  for(let i=0; i<n; i++){
    algo();
  }
}

Es evidente que es de O(n), y si yo la reescribo de esta manera:

function calcular(n) {
  let n1 = Math.ceil(Math.sqrt(n));
  let n2 = n-n1;
  for(let i=0; i <n1; i++){
    for(let j=0; j<n2; j++){
      algo();
    }
  }
}

Sigue siendo de O(n) aunque tenga 2 for

se añadieron 2 caracteres en el cuerpo
Origen Enlace
Yussef
  • 23.4k
  • 4
  • 12
  • 29

Si tienes una función:

function calcular(n) {
  n*=n
  for(let i=0; i<=n; i++){
    algo();
  }
}
function calcular(n) {
  n*=n
  for(let i=0; i<=n; i++){
    algo();
  }
}

Y digamos que calcular algo() demora siempre 1 segundo, con: |n|Tiempo (s)| |-|-| |0|0| |1|1| |2|4| |3|9| |4|16|

nTiempo (s)
00
11
24
39
416

Como se puede ver el tiempo necesario (o la cantidad de operaciones), aumenta de forma cuadrática en relación a la entrada n, por tanto esa función es de

O(n2)


La complejidad no viene dada por la cantidad de for que tenga un algoritmo, si no que por la variación de la cantidad de operaciones que realiza en relación a la entrada n

La misma función se podría escribir como

function calcular(n) {
  for(let i=0; i<n; i++){
    for(let j=0;j<n;j++){
      algo();
    }
  }
  algo();
}

Y ahí estarían los 2 for, pero esa reescritura con cambia la complejidad, la función algo() con igual entrada n se ejecuta la misma cantidad de veces en ambos casos ¿por qué deberían tener complejidades algorítmicas distintas? No tendría lógica alguna.

Y lo mismo aplica en el caso contrario, digamos que tenemos esta función

function calcular(n) {
  for(let i=0; i=n;i<n; i++){
    algo();
  }
}

Es evidente que es de O(n), y si yo la reescribo de esta manera:

function calcular(n) {
  let n1 = Math.ceil(Math.sqrt(n));
  let n2 = n-n1;
  for(let i=0; i <n1; i++){
    for(let j=0; j<n2; j++){
      algo();
    }
  }
}

Sigue siendo de O(n) aunque tenga 2 for

Si tienes una función:

function calcular(n) {
  n*=n
  for(let i=0; i<=n; i++){
    algo();
  }
}

Y digamos que calcular algo() demora siempre 1 segundo, con: |n|Tiempo (s)| |-|-| |0|0| |1|1| |2|4| |3|9| |4|16|

Como se puede ver el tiempo necesario (o la cantidad de operaciones), aumenta de forma cuadrática en relación a la entrada n, por tanto esa función es de

O(n2)


La complejidad no viene dada por la cantidad de for que tenga un algoritmo, si no que por la variación de la cantidad de operaciones que realiza en relación a la entrada n

La misma función se podría escribir como

function calcular(n) {
  for(let i=0; i<n; i++){
    for(let j=0;j<n;j++){
      algo();
    }
  }
  algo();
}

Y ahí estarían los 2 for, pero esa reescritura con cambia la complejidad, la función algo() con igual entrada n se ejecuta la misma cantidad de veces en ambos casos ¿por qué deberían tener complejidades algorítmicas distintas? No tendría lógica alguna.

Y lo mismo aplica en el caso contrario, digamos que tenemos esta función

function calcular(n) {
  for(let i=0; i=n; i++){
    algo();
  }
}

Es evidente que es de O(n), y si yo la reescribo de esta manera:

function calcular(n) {
  let n1 = Math.ceil(Math.sqrt(n));
  let n2 = n-n1;
  for(let i=0; i <n1; i++){
    for(let j=0; j<n2; j++){
      algo();
    }
  }
}

Sigue siendo de O(n) aunque tenga 2 for

Si tienes una función:

function calcular(n) {
  n*=n
  for(let i=0; i<=n; i++){
    algo();
  }
}

Y digamos que calcular algo() demora siempre 1 segundo, con:

nTiempo (s)
00
11
24
39
416

Como se puede ver el tiempo necesario (o la cantidad de operaciones), aumenta de forma cuadrática en relación a la entrada n, por tanto esa función es de

O(n2)


La complejidad no viene dada por la cantidad de for que tenga un algoritmo, si no que por la variación de la cantidad de operaciones que realiza en relación a la entrada n

La misma función se podría escribir como

function calcular(n) {
  for(let i=0; i<n; i++){
    for(let j=0;j<n;j++){
      algo();
    }
  }
  algo();
}

Y ahí estarían los 2 for, pero esa reescritura con cambia la complejidad, la función algo() con igual entrada n se ejecuta la misma cantidad de veces en ambos casos ¿por qué deberían tener complejidades algorítmicas distintas? No tendría lógica alguna.

Y lo mismo aplica en el caso contrario, digamos que tenemos esta función

function calcular(n) {
  for(let i=0; i<n; i++){
    algo();
  }
}

Es evidente que es de O(n), y si yo la reescribo de esta manera:

function calcular(n) {
  let n1 = Math.ceil(Math.sqrt(n));
  let n2 = n-n1;
  for(let i=0; i <n1; i++){
    for(let j=0; j<n2; j++){
      algo();
    }
  }
}

Sigue siendo de O(n) aunque tenga 2 for

se añadieron 1158 caracteres en el cuerpo
Origen Enlace
Yussef
  • 23.4k
  • 4
  • 12
  • 29

Digamos que calcularSi tienes una función:

  • n*=n Es constante y despreciable
  • for(let i=0; i<=n; i++) Y que cada iteración demora 1 segundo
function calcular(n) {
  n*=n
  for(let i=0; i<=n; i++){
    algo();
  }
}
nTiempo (s)
00
11
24
39
416

Y digamos que calcular algo() demora siempre 1 segundo, con: |n|Tiempo (s)| |-|-| |0|0| |1|1| |2|4| |3|9| |4|16|

Como se puede ver el tiempo necesario (o la cantidad de operaciones), aumenta de forma cuadrática en relación a la entrada n, por tanto esa función es de

O(n2)


La complejidad no viene dada por la cantidad de for que tenga un algoritmo, si no que por la variación de la cantidad de operaciones que realiza en relación a la entrada n

La misma función se podría escribir como

function calcular(n) {
  for(let i=0; i<n; i++){
    for(let j=0;j<n;j++){
      algo();
    }
  }
  algo();
}

Y ahí estarían los 2 for, pero esa reescritura con cambia la complejidad, la función algo() con igual entrada n se ejecuta la misma cantidad de veces en ambos casos ¿por qué deberían tener complejidades algorítmicas distintas? No tendría lógica alguna.

Y lo mismo aplica en el caso contrario, digamos que tenemos esta función

function calcular(n) {
  for(let i=0; i=n; i++){
    algo();
  }
}

Es evidente que es de O(n), y si yo la reescribo de esta manera:

function calcular(n) {
  let n1 = Math.ceil(Math.sqrt(n));
  let n2 = n-n1;
  for(let i=0; i <n1; i++){
    for(let j=0; j<n2; j++){
      algo();
    }
  }
}

Sigue siendo de O(n) aunque tenga 2 for

Digamos que calcular:

  • n*=n Es constante y despreciable
  • for(let i=0; i<=n; i++) Y que cada iteración demora 1 segundo
nTiempo (s)
00
11
24
39
416

Como se puede ver el tiempo necesario (o la cantidad de operaciones), aumenta de forma cuadrática en relación a la entrada n, por tanto esa función es de

O(n2)

Si tienes una función:

function calcular(n) {
  n*=n
  for(let i=0; i<=n; i++){
    algo();
  }
}

Y digamos que calcular algo() demora siempre 1 segundo, con: |n|Tiempo (s)| |-|-| |0|0| |1|1| |2|4| |3|9| |4|16|

Como se puede ver el tiempo necesario (o la cantidad de operaciones), aumenta de forma cuadrática en relación a la entrada n, por tanto esa función es de

O(n2)


La complejidad no viene dada por la cantidad de for que tenga un algoritmo, si no que por la variación de la cantidad de operaciones que realiza en relación a la entrada n

La misma función se podría escribir como

function calcular(n) {
  for(let i=0; i<n; i++){
    for(let j=0;j<n;j++){
      algo();
    }
  }
  algo();
}

Y ahí estarían los 2 for, pero esa reescritura con cambia la complejidad, la función algo() con igual entrada n se ejecuta la misma cantidad de veces en ambos casos ¿por qué deberían tener complejidades algorítmicas distintas? No tendría lógica alguna.

Y lo mismo aplica en el caso contrario, digamos que tenemos esta función

function calcular(n) {
  for(let i=0; i=n; i++){
    algo();
  }
}

Es evidente que es de O(n), y si yo la reescribo de esta manera:

function calcular(n) {
  let n1 = Math.ceil(Math.sqrt(n));
  let n2 = n-n1;
  for(let i=0; i <n1; i++){
    for(let j=0; j<n2; j++){
      algo();
    }
  }
}

Sigue siendo de O(n) aunque tenga 2 for

Origen Enlace
Yussef
  • 23.4k
  • 4
  • 12
  • 29
Loading