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