[Quema]

Si tengo esta tarea:

1)   Ingresar \( n \) valores \( x_1, x_2,…,x_n \) y sus respectivas probabilidades \( p_1,p_2,…,p_n. \)
2)   Ingresar la función \( u(x)  \) y \( w(x) \) ambas crecientes y cóncavas
3)   Calcular \( u(x_i) \) para cada \(  i=1,2,…,n \)
4)   Calcular \( g(x_i)=w(p_1+…+p_i)-w(p_1+p_2+…+p_{i-1}) \) para \(  i=1,2,…,n \)
5)   Calcular \( \displaystyle\sum_{i=1}^n{}u(x_i)g(x_i) \)

Cuál es el tiempo de complejidad? Puede ser \( O(n) \).

[Luis Fuentes]

Hola

Si tengo esta tarea:

1)   Ingresar \( n \) valores \( x_1, x_2,…,x_n \) y sus respectivas probabilidades \( p_1,p_2,…,p_n. \)
2)   Ingresar la función \( u(x)  \) y \( w(x) \) ambas crecientes y cóncavas

La toma de datos no se suele tener en cuenta para el tiempo de computación.

3)   Calcular \( u(x_i) \) para cada \(  i=1,2,…,n \)

\( n \) veces el coste de calcular \( u \). Eso depende de \( u \).

\( n\cdot coste(u) \)

4)   Calcular \( g(x_i)=w(p_1+…+p_i)-w(p_1+p_2+…+p_{i-1}) \) para \(  i=1,2,…,n \)

Para cada \( i \) son \( i-1+1+i-2=2i-2 \) operaciones más dos veces evaluar \( w \).

En total:\( n(n-1)+2n\cdot coste(w) \)

5)   Calcular \( \displaystyle\sum_{i=1}^n{}u(x_i)g(x_i) \)

\( (n-1)(coste(u)+coste(g)+1) \)

En total:

\( n\cdot coste(u)+\color{red}n(n-1)+2n\cdot coste(w)\color{black}+(n-1)(coste(u)+coste(g)+1) \)

En principio. Es de orden \( O(n^2) \).

Ahora bien. Realmente aquí:

4)   Calcular \( g(x_i)=w(p_1+…+p_i)-w(p_1+p_2+…+p_{i-1}) \) para \(  i=1,2,…,n \)

No hace falta repetir el cáculo de las sumas de cada vez.

Es decir previamente podemos calcular \( s_1,s_2,\ldots,s_n \). Con \( s_1=p_1 \) y \( s_k=s_{k-1}+p_k \). Esto son \( n-1 \) operaciones. Luego calcular:

 \( g(x_i)=w(s_i)-w(s_{i-1}) \)

que son \( n(2coste(w)+1) \).

Ahora quedaría en total:

\( n\cdot coste(u)+\color{red}2n-1+2n\cdot coste(w)\color{black}+(n-1)(coste(u)+coste(g)+1) \)

que es de orden \( O(n) \).

Saludos.

[Quema]

El coste de ingresar una función, supongamos \( u(x)=\sqrt[ ]{x} \) es de orden 1, según tengo entendido. Voy a poner un ejemplo, para explicarme mejor. Supongamos que tengo \( w(p)=p^2 \) y tengo una variable aleatoria \( X \) que toma valores 38, 39, 40, 41 y 42 con probabilidades 1/5, 1/4, 1/3, 1/6 y 1/20 respectivamente. Defino otra variable aleatoria \( Y=(40.5-X)h+65.000X-2.000.000. \) Siendo un \( h \) un parámetro, supongamos entero, que va de \( [0,90.000] \).

Ahora la clave está, algo que he preguntado en el otro lado del foro es que los valores de \( Y \) tienen que estar ordenados de forma decreciente y luego se aplican los pesos tal cual he preguntado en esta pregunta. Por ejemplo, supongamos que \( h=0 \) entonces

\( Y \) puede tomar valores 470.000, 535.000, 600.000, 665.000 y 730.000 con probabilidades 1/5, 1/4, 1/3, 1/6 y 1/20 respectivamente, no?.

Entonces \( RDU(Y(0))=u(730.000)(1/20)^2+u(665.000)((1/20+1/6)^2-(1/20)^2)+u(600.000)((1/20+1/6+1/3)^2-(1/20+1/6)^2)+...+u(470.000)(1-(1/20+1/6+1/3+1/4)^2) \)

Cuidado que no en todos los casos de \( h \) tenemos que los valores que toma \( Y \) ya están de alguna forma ordenados, entonces yo creo que partiendo de los valores de \( X \) y sus probabilidades respectivas, el orden de complejidad de este cálculo será, en primer lugar determinar las regiones donde esas rectas se cortan que tiene orden \( O((n+k)\log n) \) siendo \( k \) la candidad de intersecciones que como máximo serán \( \displaystyle\frac{n(n1-1)}{2} \) cortes. Segundo lugar el orden de forma decreciente los valores obtenidos que tendrá un orden de \( O(n\log n) \) y luego las diferencias entre los \( w \) para cada región como habrán como màximo \( \displaystyle\frac{n(n1-1)}{2}+1 \) regiones el peor escenario es un orden \( O(\frac{n(n1-1)}{2}+1)n)=O(n^3) \).

Es decir el orden total de esta operaciòn será el mayor entre \( O((n+k)\log n) \) y \( O(n^3). \)

Está bien?


PD No me queda claro en el paso 5, pq pones \( O(n^2) \) yo entiendo que son solamente \( n \) suma debería de ser orden \( n \). En resumen, en mi primera pregunta si los \( x_i \) ya estuvieran ordenados de forma decreciente el orden serìa \( n \) si no lo fueran debería ser el orden de ordenarlos, que por lo que vi el peor orden es \( O(n \log n) \).

[Luis Fuentes]

Hola

Ahora la clave está, algo que he preguntado en el otro lado del foro es que los valores de \( Y \) tienen que estar ordenados de forma decreciente y luego se aplican los pesos tal cual he preguntado en esta pregunta. Por ejemplo, supongamos que \( h=0 \) entonces

\( Y \) puede tomar valores 470.000, 535.000, 600.000, 665.000 y 730.000 con probabilidades 1/5, 1/4, 1/3, 1/6 y 1/20 respectivamente, no?.

Entonces \( RDU(Y(0))=u(730.000)(1/20)^2+u(665.000)((1/20+1/6)^2-(1/20)^2)+u(600.000)((1/20+1/6+1/3)^2-(1/20+1/6)^2)+...+u(470.000)(1-(1/20+1/6+1/3+1/4)^2) \)

Cuidado que no en todos los casos de \( h \) tenemos que los valores que toma \( Y \) ya están de alguna forma ordenados,

No entiendo esta frase.

entonces yo creo que partiendo de los valores de \( X \) y sus probabilidades respectivas, el orden de complejidad de este cálculo será, en primer lugar determinar las regiones donde esas rectas se cortan que tiene orden \( O((n+k)\log n) \) siendo \( k \) la candidad de intersecciones que como máximo serán \( \displaystyle\frac{n(n1-1)}{2} \) cortes.

No entiendo a que rectas y a que cortes te refieres. ¿Quién es \( n_1 \)?.

PD No me queda claro en el paso 5, pq pones \( O(n^2) \) yo entiendo que son solamente \( n \) suma debería de ser orden \( n \). En resumen, en mi primera pregunta si los \( x_i \) ya estuvieran ordenados de forma decreciente el orden serìa \( n \) si no lo fueran debería ser el orden de ordenarlos, que por lo que vi el peor orden es \( O(n \log n) \).

El \( n^2 \) viene del término en rojo del paso 4:

4)   Calcular \( g(x_i)=w(p_1+…+p_i)-w(p_1+p_2+…+p_{i-1}) \) para \(  i=1,2,…,n \)

Para cada \( i \) son \( i-1+1+i-2=2i-2 \) operaciones más dos veces evaluar \( w \).

En total:\( \color{red}n(n-1)\color{black}+2n\cdot coste(w) \)

Pero luego también te he aclarado que si esas sumas \( p_1+\ldots+p_k \) se dejan guardadas y no se repiten de cada vez, el orden pasa de O(n^2) a O(n).

4)   Calcular \( g(x_i)=w(p_1+…+p_i)-w(p_1+p_2+…+p_{i-1}) \) para \(  i=1,2,…,n \)

No hace falta repetir el cáculo de las sumas de cada vez.

Es decir previamente podemos calcular \( s_1,s_2,\ldots,s_n \). Con \( s_1=p_1 \) y \( s_k=s_{k-1}+p_k \). Esto son \( n-1 \) operaciones. Luego calcular:

 \( g(x_i)=w(s_i)-w(s_{i-1}) \)

que son \( n(2coste(w)+1) \).

Ahora quedaría en total:

\( n\cdot coste(u)+\color{red}2n-1+2n\cdot coste(w)\color{black}+(n-1)(coste(u)+coste(g)+1) \)

que es de orden \( O(n) \).

Saludos.

[Quema]

Partiendo de mi pregunta inicial, si para aplicar todo este procedimiento, los \( x_i \) y sus correspondientes probabilidades, supongamos que deberían estar ordenados de forma decreciente respecto a los valores de \( x_i \). En resumen, si estos ya estuvieran ordenados el orden es \( n \), si no lo estuvieran y supongamos que ingreso los pares \( (x_i,p_i) \) el orden de obtener \( RDU(X) \) será el orden de ordenar esos pares que será \( O(n \log n) \), bien?

Ahora, supuse que quiero calcular el \( RDU(Y) \) siendo Y una v.a. definida más arriba que depende de un parámetro \( h \). Este parámetro hace que los valores de \( y_i \) y por lo tanto su orden varíe ante variaciones de \( h \). Es decir, debería ver las regiones de \( h \) tal que supongamos \( y_1(h)\geq y_2(h)\geq...\geq y_5 \), pero hay otras regiones donde por ejemplo ese orden cambia. Cuántas regiones de \( h \) habrá? Bueno, tengo que analizar cuántas intersecciones de esas rectas tenemos. Y para \( n \) rectas tendremos como máximo \( \displaystyle\frac{n(n-1)}{2} \) intersecciones en un mismo plano. Es decir, habría \( \displaystyle\frac{n(n-1)}{2}+1 \) regiones de \( h \) donde debería analizar el orden de los \( y_i(h) \). Hacer esto tiene orden \( O((n+k)\log n) \) siendo \( k \) el número de intersecciones de las rectas. De acuerdo?
Mi pregunta, cuál es el orden de calcular \( RDU(Y(h)) \)? Creo que es el máximo entre \( O(n^3) \) y \( O(n^2\log(n)) \).

[Luis Fuentes]

Hola

Partiendo de mi pregunta inicial, si para aplicar todo este procedimiento, los \( x_i \) y sus correspondientes probabilidades, supongamos que deberían estar ordenados de forma decreciente respecto a los valores de \( x_i \). En resumen, si estos ya estuvieran ordenados el orden es \( n \), si no lo estuvieran y supongamos que ingreso los pares \( (x_i,p_i) \) el orden de obtener \( RDU(X) \) será el orden de ordenar esos pares que será \( O(n \log n) \), bien?

Si.

Ahora, supuse que quiero calcular el \( RDU(Y) \) siendo Y una v.a. definida más arriba que depende de un parámetro \( h \). Este parámetro hace que los valores de \( y_i \) y por lo tanto su orden varíe ante variaciones de \( h \). Es decir, debería ver las regiones de \( h \) tal que supongamos \( y_1(h)\geq y_2(h)\geq...\geq y_5 \), pero hay otras regiones donde por ejemplo ese orden cambia. Cuántas regiones de \( h \) habrá? Bueno, tengo que analizar cuántas intersecciones de esas rectas tenemos. Y para \( n \) rectas tendremos como máximo \( \displaystyle\frac{n(n-1)}{2} \) intersecciones en un mismo plano. Es decir, habría \( \displaystyle\frac{n(n-1)}{2}+1 \) regiones de \( h \) donde debería analizar el orden de los \( y_i(h) \). Hacer esto tiene orden \( O((n+k)\log n) \) siendo \( k \) el número de intersecciones de las rectas. De acuerdo?

Pero si \( Y \) se define como dices es lineal:

\( Y=(40.5-X)h+65.000X-2.000.000=(65000-h)X+cte \)

Si los \( X \) están ordenados, los \( Y \) también. El orden será el mismo que \( X \) u opuesto, dependiendo del signo de \( 65000-h \), pero en cualquier caso no habría que volver a ordenar.

Incluso si \( Y \) no es lineal conociendo sus intervalos de crecimiento, puede aprovecharse que los \( X \) estén ordenados para fácilmente ordenar los valores de \( Y \). Pero no se si he entendido bien.

Mi pregunta, cuál es el orden de calcular \( RDU(Y(h)) \)? Creo que es el máximo entre \( O(n^3) \) y \( O(n^2\log(n)) \).

Si fuese el caso, el máximo de esos dos es \( O(n^3) \).

Saludos.

[Quema]

No, me explico nuevamente.

Si \( x_1=38 \) entonces \( y_1=2.5h+470.000 \) con probabilidad \( 1/5 \), \( x_2=39 \) entonces \( y_2=1.5h+535.000 \) con probabilidad \( 1/4 \), si \( x_3=40 \) entonces \( y_3=0.5h+600.000 \), \( y_4=-0.5h+600.000 \) y \( y_5=-1.5h+730.000 \) con probabilidades \( 1/3, 1/6, 1/20 \) respectivamente. Ahora, supongamos que \( h \) es un entero entre \( [0,90.000] \) Cuando \( h \) cambia entonces cambia el orden de los \( y_i(h) \) como estos tienen que estar ordenados de forma decreciente tengo que analizar las regiones de los \( h \) para saber su orden, antes de aplicar la fórmula de la primera pregunta.

Por ejemplo si \( h=25.000 \) tenemos que \( y_5(25.000)>y_3(25.000)>y_4(25000)>y_3(25000)>y_1(25000)>y_2(25000). \)

De ahí que determinar todas las regiones tiene orden \( O((n+k)\log n) \) y luego realizar los cálculos de los \( w(p_1+…+p_i)-w(p_1+p_2+…+p_{i-1})
 \) (sabiendo que como cambia el orden, cambian los sumandos \( p_i \)), para todas las regiones, eso tiene orden \( O(n^3). \)

Para \( h=25000 \) empezaría con \( u(y_5(25000))w(1/20)+u(y_3(25000))(w(1/20+1/3)-w(1/20))+... \)

Importante en la secuencia de etapas ingresar el \( h \) no es en la primera etapa sino antes de determinar \( RDU(Y(h)) \), pues despuès necesitaré maximizar. Pues si en la primera etapa ya tengo \( h \) entonces si el orden será el mismo que en el de la primera pregunta, no? El motivo?, es que luego necesito maximizar \( RDU(Y(h)) \) respecto a \( h \). Aunque no estoy muy seguro de esto, le orden de calcular \( RDU(Y(h)) \) tiene que ser mayor que el de \( RDU(X) \) por el molesto parámetro \( h \).

Obviamente si el primer paso es ingresar el valor de \( h=h^* \) entonces el orden será el mismo de ordenar los \( y_i(h^*) \) que será \( O(n\log(n)) \). Pero mi pregunta es si ingresara el \( h \) al final, no se si me explico. Lo pongo de otra forma, con estos datos quiero hallar el \( h \) que maximice \( RDU(Y(h)) \) y el orden de ese algoritmo.

[Luis Fuentes]

Hola

No, me explico nuevamente.

Si \( x_1=38 \) entonces \( y_1=2.5h+470.000 \) con probabilidad \( 1/5 \), \( x_2=39 \) entonces \( y_2=1.5h+535.000 \) con probabilidad \( 1/4 \), si \( x_3=40 \) entonces \( y_3=0.5h+600.000 \), \( y_4=-0.5h+600.000 \) y \( y_5=-1.5h+730.000 \) con probabilidades \( 1/3, 1/6, 1/20 \) respectivamente. Ahora, supongamos que \( h \) es un entero entre \( [0,90.000] \) Cuando \( h \) cambia entonces cambia el orden de los \( y_i(h) \) como estos tienen que estar ordenados de forma decreciente tengo que analizar las regiones de los \( h \) para saber su orden, antes de aplicar la fórmula de la primera pregunta.

Por ejemplo si \( h=25.000 \) tenemos que \( y_5(25.000)>y_3(25.000)>y_4(25000)>y_3(25000)>y_1(25000)>y_2(25000). \)

Pues debo de estar obcecado porque no lo veo.

Parece que estás aplicando está fórmula:

\( Y=(40.5-X)h+65000X-2000000=(65000-h)X-2000000+40.5\cdot h \)

Para \( x=38 \) queda \( y=470000 + 2.5 h \)
Para \( x=39 \) queda \( y=535000 + 1.5 h \)
Para \( x=40 \) queda \( y=600000 + 0.5 h \)
Para \( x=41 \) queda \( y=665000 - 0.5 h \) (aquí tu pones 60000 ,pero está mal)
Para \( x=42 \) queda \( y=730000 - 1.5 h \)

etcétera

Entonces fijado \( h \) eso es una recta...¡entonces o conserva el orden de los \( x \) o lo invierte! ¡No hay más!.

Ese orden raro que te da es por culpa del error en el \( y_4 \).

Saludos.

[Quema]

Si claro, qué tonto, cortan todas en \( h=65.000 \). Pregunto, supongamos que quisiera hallar el \( h \) que maximiza \( RDU(Y(h)) \), cuál es el orden del tiempo de complejidad.

PD  Mi pregunta es extender esto a un caso màs general, donde haya \( n \) rectas (generados por una v.a. \( X \) que toma \( n \) valores discretos) y donde existan \( \displaystyle\frac{n(n-1)}{2} \) puntos de intersección y quiero hallar el máximo de \( RDU(Y(h)) \) y determinar el tiempo de complejidad para ese caso.

[Quema]

Me voy respondiendo, de la forma que planteé \( y_i(h)=(\theta-x_i)h+x_i \) entonces \( n \) rectas cortarán en el mismo punto, y por lo tanto el tiempo de complejidad será \( O((n+1)\log n)=O(n\log n) \), no? Ahora mi duda está en el cálculo de \( g(x_i)=w(p_1+…+p_i)-w(p_1+p_2+…+p_{i-1}) \), ahí tendría que hacerlo en dos tramos, no estoy muy seguro del orden, si es \( O(2n)=O(n) \)

Por otro lado, supongamos que pudiera haber \( n \) rectas donde hay \( R=\displaystyle\frac{n(n-1)}{2} \) puntos de intersección, nos llevaría \( O(n^2\log n) \) encontrar todos los puntos de interseción. Como habría \( R+1 \) regiones y entonces calcular los \( g(x_i) \) insumiría un tiempo \( O(Rn)=O(n^3) \). Luego tendría que ordenar de forma decreciente a los \( y_i(h) \)  que lleva un tiempo \( O(n\log n) \), por eso creo que maximizar llevaría un tiempo del mayor entre \( O(n^2 \log n) \) y \( O(n^3) \), que es \( O(n^3) \), está bien?