0

Necesito saber la complejidad O(f) de este algoritmo que consiste en un ciclo doble.

Según he estudiado, su complejidad debería ser O(n^2) debido a que se están anidando bucles, el problema es que el bucle más externo tiene como límite un número explícito, por lo que su complejidad debería ir a O(n).

Quisiera saber si mi deducción es correcta o la complejidad es otra. Gracias.

Entero i, n, x, k, Sum;
Real Prod;
Prod = 1;

Para i = n hasta 1 en -1 hacer
   Sum = 0;
      Para k = i hasta n en 1 hacer
         Sum = Sum + (i*k – n*x)^2;
      FPara;
         Prod = Prod * ( (n/x) + Sum );
FPara;

1 respuesta 1

1

En el ciclo exterior, el límite no es un número explícito, sólo estás decrementando desde un valor N hasta 1. Decrementas por un valor constante a partir de un valor que cambia dependiendo de N hasta llegar a 1 y eso siempre es O(n) (lo ejecutas N veces, ¿no?).

Así pues, la cantidad de veces que el ciclo interior se ejecuta nos da la pista y el par de ciclos anidados efectivamente es O(n^2). Te queda decidir si lo que está dentro de los ciclos anidados es O(1); también te queda revisar qué pasa con Prod = Prod * ( (n/x) + Sum ); (acostúmbrate a indentar el código correctamente para que no pierdas de vista cosas)

1
  • Gracias. Y sí, efectivamente después de analizarlo mejor concluí que era O(n**2).
    – SpectrumZX
    Commented el 28 abr. 2022 a las 23:42

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.