Autor Tema: Índice de sumatorias para calcular orden de un algoritmo

0 Usuarios y 1 Visitante están viendo este tema.

25 Mayo, 2019, 10:24 pm
Leído 709 veces

serdel

  • Nuevo Usuario
  • Mensajes: 22
  • Karma: +0/-0
  • Sexo: Masculino
Hola,no se como podria aplicar las propiedas de sumatorias para llegar a calcular el orden en un algoritmo.
Por ejemplo, me dieron un algoritmo del cual me queda una expresion asi:

\(  C_1+\displaystyle\sum_{i=1}^{n-1}\sum_{J=i+1}^{j<=n} \sum_{k=1}^{k<=j} + C_2 \)

Como se resuelven los indices?

27 Mayo, 2019, 09:28 am
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,066
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Hola,no se como podria aplicar las propiedas de sumatorias para llegar a calcular el orden en un algoritmo.
Por ejemplo, me dieron un algoritmo del cual me queda una expresion asi:

\(  C_1+\displaystyle\sum_{i=1}^{n-1}\sum_{J=i+1}^{j<=n} \sum_{k=1}^{k<=j} + C_2 \)

Como se resuelven los indices?

¿Qué es lo que estás sumando?¿ \( +C_2 \)?¿Eso es una constante que no depende de los índices?.

Saludos.

27 Mayo, 2019, 03:33 pm
Respuesta #2

serdel

  • Nuevo Usuario
  • Mensajes: 22
  • Karma: +0/-0
  • Sexo: Masculino
Hola Luis, perdon. Copie mal, esa constante C_2 esta dentro de la sumatoria, por lo que me quedaria asi:

\( C_1 + \displaystyle\sum_{i=1}^{n-1} \displaystyle\sum_{j=i + 1}^{j<=k} \displaystyle\sum_{k=1}^{k<=j} C_2 \)

28 Mayo, 2019, 10:33 am
Respuesta #3

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,066
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Hola Luis, perdon. Copie mal, esa constante C_2 esta dentro de la sumatoria, por lo que me quedaria asi:

\( C_1 + \displaystyle\sum_{i=1}^{n-1} \displaystyle\sum_{j=i + 1}^{j<=k} \displaystyle\sum_{k=1}^{k<=j} C_2 \)

Todavía hay algo mal. No puede ser que en los límites de \( j \) aparezca \( k \), que aun no está definido.  Los sumatorios interiores tienen que tener límites que dependan de variables previamente usadas en los sumatorios exteriores. Revisa bien los límites.

Saludos.

28 Mayo, 2019, 01:32 pm
Respuesta #4

serdel

  • Nuevo Usuario
  • Mensajes: 22
  • Karma: +0/-0
  • Sexo: Masculino
Si, es asi:

\( c_1 \displaystyle\sum_{i=1}^{n-1} \displaystyle\sum_{j=i+1}^{n}\displaystyle\sum_{k=1}^{n} c_2 \)

Por que el codigo es asi:
constante

for ( i=1; i <= n-1; i++)
      for(j= i+1; j<= n; j++)
           for (k=1; k<= j; k++)
                  constante

28 Mayo, 2019, 04:21 pm
Respuesta #5

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,066
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Si, es asi:

\( c_1 \displaystyle\sum_{i=1}^{n-1} \displaystyle\sum_{j=i+1}^{n}\displaystyle\sum_{k=1}^{n} c_2 \)

Por que el codigo es asi:
constante

for ( i=1; i <= n-1; i++)
      for(j= i+1; j<= n; j++)
           for (k=1; k<= j; k++)
                  constante

Si es como indicas en los bucles anidados sería:

\( \displaystyle\sum_{i=1}^{n-1} \displaystyle\sum_{j=i+1}^{n}\displaystyle\sum_{k=1}^{\color{red}j\color{black}} c_2=c_2\displaystyle\sum_{i=1}^{n-1} \displaystyle\sum_{j=i+1}^{n}\displaystyle\sum_{k=1}^{\color{red}j\color{black}}1 \)

Ahora:

\( \displaystyle\sum_{i=1}^{n-1} \displaystyle\sum_{j=i+1}^{n}\displaystyle\sum_{k=1}^{j}1=\displaystyle\sum_{i=1}^{n-1} \displaystyle\sum_{j=i+1}^{n}j=\displaystyle\sum_{i=1}^{n-1} \dfrac{(n+i+1)(n-i)}{2}=\displaystyle\sum_{i=1}^{n-1}\dfrac{n^2+n-i^2-i}{2}=\\=\dfrac{n^2+n}{2}\displaystyle\sum_{i=1}^{n-1}1-\dfrac{1}{2}\displaystyle\sum_{i=1}^{n-1}(i^2+i)=\dfrac{(n^2+n)(n-1)}{2}-\dfrac{1}{2}\left(\dfrac{(n-1)n(2n-1)}{6}+\dfrac{n(n-1)}{2}\right)=\dfrac{1}{3}n(n^2-1) \)

Saludos.

28 Mayo, 2019, 05:44 pm
Respuesta #6

serdel

  • Nuevo Usuario
  • Mensajes: 22
  • Karma: +0/-0
  • Sexo: Masculino
Gracias, estoy intentando entender cada paso. Ahi marque en con rojo y no entiendo por que pusiste el termino (n - i)









28 Mayo, 2019, 05:58 pm
Respuesta #7

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,066
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Gracias, estoy intentando entender cada paso. Ahi marque en con rojo y no entiendo por que pusiste el termino (n - i)

Estoy usando la fórmula de la suma de unos términos de una progresión aritmética:

\( S=\dfrac{a_1+a_k}{2}\cdot k \)

donde \( a_1,a_k \) son respectivamente el primer y último término y \( k \) el número de términos.

En nuestro caso:

\( a_1=i+1,\qquad a_k=n,\qquad k=n-(i+1)+1 \)

Más adelante también uso la fórmula de la suma de cuadrados:

\( \displaystyle\sum_{k=1}^n{}k^2=\dfrac{n(n+1)(2n+1)}{6} \)

Saludos.

P.D. Evita fórmulas en archivos adjuntos.