1

¿Qué complejidad algorítmica tiene este código?

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

En especifico tengo la duda si es de O(n) o O(n2). He buscado en internet y he encontrado ambas respuestas en foros y en blogs, en cambio no he podido encontrar un ejemplo similar en documentación bibliográfica.

Lo más cercano que he encontrado es en el libro Introducción a los algoritmos de Thomas H. Cormen, donde hay un ejemplo que el for llega hasta √n y donde da que su complejidad es de O(√n)

Si uno grafica el número de iteraciones de un for que va hasta 2*n se dará cuenta que es una función lineal solo que la pendiente cambia, lo cual si se puede decir que es lineal porque la propia definición de Big-O incluye una constante multiplicada por g(x) para esos casos pero si el número de iteraciones crece de manera cuadrática ya ahí si no podríamos decir que es lineal. Ahí está mi gran duda

19
  • Mira Cómo preguntar para que tu pregunta sea mejor recibida. También, aprovecha y haz el recorrido de bienvenida para entender mejor cómo funcionamos y de paso obtener tu primera medalla! pues... eso es una iteracion.. no hay mucha complejidad ahi... creo que esta no es tu pregunta en si.. que es lo que queres preguntar realmente?? porque esto, esta hasta en google...
    – gbianchi
    Commented el 28 ene. a las 0:21
  • @gbianchi el algoritmo tiene complejidad lineal O(n), no entiendo pq cerraste la pregunta, me parece válida y respondíble, la complejidad algorítmica es toda una ciencia dentro de las ciencias de la computación, además el op no busca ni libros ni recomendaciones
    – Japv
    Commented el 28 ene. a las 0:24
  • Stackoverflow fue quien la cerró, por qué es lineal? La primera linea no afecta a la n del ciclo for? O sea mi duda es si n=n*n afecta a la n del for haciendonlo ir hasta n^2
    – Lenar
    Commented el 28 ene. a las 0:30
  • @Japv mira el historial.antes de la edicion pedia libros sobre el tema. Aunque la complejidad algoritmica es un tema en si, y valido, es valido si hay un intento no? un for, no tiene complejidad algoritmica... no? o es siempre igual.. no?
    – gbianchi
    Commented el 28 ene. a las 0:36
  • La primera línea tiene un orden constante, y no afecta al ciclo
    – Japv
    Commented el 28 ene. a las 0:37

1 respuesta 1

1

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

4
  • Los comentarios han sido movidos al chat; por favor, no continuar la discusión aquí. Antes de publicar un comentario bajo este, por favor revisa los propósitos de los comentarios. Los comentarios que no pidan clarificaciones o sugieran mejoras normalmente deben ser publicados como una respuesta, en Stack Overflow Meta en español, o en el Chat de Stack Overflow en español. Los comentarios que continúen la discusión podrán ser eliminados.
    – gbianchi
    Commented el 28 ene. a las 21:53
  • @Yussef ya te di mi +1, revisé los enlaces que dejaste en el chat, releí tú respuesta y busque información, analice con más detalle y profundidad y saque conclusiones y finalmente asumo que tu explicación es correcta, felicidades y disculpa cualquier molestia ocasionada, fue un buen debate
    – Japv
    Commented el 28 ene. a las 23:42
  • @Yussef puede agregar aqui los link por favor es importante incluir documentacion en las respuesta para sustentar y evitar estas diferencias, saludos. Commented el 29 ene. a las 21:13
  • @Yussef gracias por editar, es que estaba ocupado
    – Lenar
    Commented el 30 ene. a las 1:04

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.