[dificildeolvidar]

Hola, tengo que realizar este ejercicio para calcular la complejidad algorítmica. Pero no me queda claro la instrucción que está más adentro, ¿cómo se estudiaría?
El primer for sé que va de 1 a n, el segundo de i+1 a n, ¿pero y lo de dentro?
¿Cómo se realizaría un sumatorio de este código?

Para i=1...n-1
para j=i+1....n
j-i+1

Los dos for los tengo claros (el primer for se recorre n-1 veces, el segundo se va decrementando es decir en la primera iteración se recorre n-1, en la segunda n-2 en la tercera n-3 y así hasta 1) lo que no se analizar es el i-j+1.
Tendría que solucionar la serie aritmética y calcularla para calcular la complejidad.

[Fallen Angel]

No es importante para la complejidad la suma j-i+1 , lo importante es el numero de pasos que des.

Digamos que la operación (j-i+1) es una operación elemental.

Entonces la complejidad de tu algoritmo será el numero de sumandos que tienes que realizar, es decir, el numero de pasos que das.

La primera vez que entras en el primer lazo realizas n-2 operaciones elementales.

La segunda vez que entras realizas n-3 operaciones elementales.

Y sigue sucesivamente hasta la última vez que entras y realizas una operación.

Por tanto el número de pasos es \( \displaystyle\sum_{i=1}^{n-1}n-i-1=\displaystyle\sum_{i=2}^{n}n-i=n(n-2)-\displaystyle\sum_{i=2}^{n}i=n(n-2)-(\dfrac{n(n+1)}{2}-1) \).

Un saludo!

[dificildeolvidar]

No es importante para la complejidad la suma j-i+1 , lo importante es el numero de pasos que des.

Digamos que la operación (j-i+1) es una operación elemental.

Entonces la complejidad de tu algoritmo será el numero de sumandos que tienes que realizar, es decir, el numero de pasos que das.

La primera vez que entras en el primer lazo realizas n-2 operaciones elementales.

La segunda vez que entras realizas n-3 operaciones elementales.

Y sigue sucesivamente hasta la última vez que entras y realizas una operación.

Por tanto el número de pasos es \( \displaystyle\sum_{i=1}^{n-1}n-i-1=\displaystyle\sum_{i=2}^{n}n-i=n(n-2)-\displaystyle\sum_{i=2}^{n}i=n(n-2)-(\dfrac{n(n+1)}{2}-1) \).

Un saludo!

Entonces desarrollando lo que te me has puesto, la final la solución=\( \dfrac{n^2-n}{2} \) que pertenece a complejidad \( n^2 \), ¿no?
 Pero es que yo creo que la j va cambiando su valor en la última instrucción por la tanto va cambiando su recorrido en el bucle, de hecho he implementado el código y el valor de j y por lo tanto el número de iteraciones cambia. Ya no depende del valor del segundo bucle solo.
Eso es lo que no entiendo.
Graciasss!!!

[Luis Fuentes]

Hola

Pero es que yo creo que la j va cambiando su valor en la última instrución por la tanto va cambiando su recorrido en el bucle, de hecho he implementado el código y el valor de j y por lo tanto el número de iteraciones cambia. Ya no depende del valor del segundo bucle solo.

¿Por qué dices que \( j \) cambia su valor?

La última instrucción solo pone:

\( j-i+1 \)

¿Dónde está el cambio de valor de \( j \)?.

Por ejemplo para \( n=3 \) sería.

\( i=1, j=2 \) hacemos la cuenta \( j-i+1=2-1+1=2 \)
\( i=1, j=3 \) hacemos la cuenta \( j-i+1=3-1+1=3 \)
\( i=2, j=3 \) hacemos la cuenta \( j-i+1=3-2+1=2 \)

Saludos.

[dificildeolvidar]

Hola

Pero es que yo creo que la j va cambiando su valor en la última instrución por la tanto va cambiando su recorrido en el bucle, de hecho he implementado el código y el valor de j y por lo tanto el número de iteraciones cambia. Ya no depende del valor del segundo bucle solo.

¿Por qué dices que \( j \) cambia su valor?

La última instrucción solo pone:

\( j-i+1 \)

¿Dónde está el cambio de valor de \( j \)?.

Por ejemplo para \( n=3 \) sería.

\( i=1, j=2 \) hacemos la cuenta \( j-i+1=2-1+1=2 \)
\( i=1, j=3 \) hacemos la cuenta \( j-i+1=3-1+1=3 \)
\( i=2, j=3 \) hacemos la cuenta \( j-i+1=3-2+1=2 \)

Saludos.

Yo resuelvo este tipo de ejercicios haciendo una traza y una vez que calculo la fórmula para un número general calculo el sumatorio, te paso la traza que he hecho para ver si está bien.

[dificildeolvidar]

No es importante para la complejidad la suma j-i+1 , lo importante es el numero de pasos que des.

Digamos que la operación (j-i+1) es una operación elemental.

Entonces la complejidad de tu algoritmo será el numero de sumandos que tienes que realizar, es decir, el numero de pasos que das.

La primera vez que entras en el primer lazo realizas n-2 operaciones elementales.

La segunda vez que entras realizas n-3 operaciones elementales.

Y sigue sucesivamente hasta la última vez que entras y realizas una operación.

Por tanto el número de pasos es \( \displaystyle\sum_{i=1}^{n-1}n-i-1=\displaystyle\sum_{i=2}^{n}n-i=n(n-2)-\displaystyle\sum_{i=2}^{n}i=n(n-2)-(\dfrac{n(n+1)}{2}-1) \).

Un saludo!

Me parece que te has equivocado, ya que en la primera vez que se entra en el primer lazo se realizan n-1 operaciones elementales, la segunda vez n-2 la tercera n-3 y así sucesivamente hasta 1. Por lo tanto el sumatorio sería \( \displaystyle\sum_{i=1}^{n-1}n-i\displaystyle  \)
He realizado una traza del ejercicio te la paso para ver si está bien.

[Fallen Angel]

Sí me he equivocado , en cada paso hay una suma más de las que yo he puesto, pero en cualquier caso la complejidad algoritmica es de \( \mathcal{O}(n^{2}) \).

En esa tabla lo único que haces es razonar como lo he hecho yo, sólo que escribiendo explícitamente cada paso, en cualquier caso hay un error, en la última fila de todo, si i=n-1, j=n haces una operación.

Un saludo!

[Víctor Luis]

Holas...

• Segun los temas que lei, tu complejidad asintótica es exponencial
\( O(n^2) \)
Debido a que tienes un bucle For dentro de otro, donde si tuvieras un tercer bucle interno tu complejidad seria:
\( O(n^3) \)
es una referencia practica, para saber el tipo de complejidad que tiene un algoritmo.

[Fallen Angel]

• Segun los temas que lei, tu complejidad asintótica es exponencial
\( O(n^2) \)

Polinómica, si enlazar dos bucles supusiese complejidad exponencial no habría forma de programar nada útil.

[Víctor Luis]

Correcto, la complejidad polinomica es temporal:
\( O(p(n)) \)
donde n es el tamaño o limite de la entrada, que determinará el tiempo del proceso del algoritmo.