[Luis Fuentes]

Hola

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) \)

Es lo mismo \( O(2n) \) que \( O(n) \). Esa constante es lo de menos. Técnicamente si \( \displaystyle\lim_{x \to{+}\infty}\dfrac{f(n)}{g(n)}=k\neq 0 \) entonces \( O(f(n))=O(g(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) \).

Es que no acabo de entender lo de hallar los puntos de intersección de esas rectas; no se a que viene y para que lo haces. Sobre todo si después igualmente vas a ordenar los \( y_i \).

Saludos.

[Quema]

A ver, dime detallando paso a paso y el tiempo de complejidad que harias tu para hallar ese máximo. Tienes que tener cuidado, que los \( g(x_i) \) dependen de la probabilidad de los \( x_i \) y de su ranking (posición). Es por esto el motivo que hay que calcular todas las regiones de \( h \) donde cambian las posiciones de los \( y_i(h) \), pues al variar su ranking varían los \( g(x_i). \) No se si me expliqué bien. Es decir, un ejemplo con tres valores si tengo que \( x_1\geq x_2\geq x_3 \) con probabilidades \( p_1,p_2, p_3 \) entonces el funcional:

\( RDU=u(x_1)w(p_1)+u(x_2)(w(p_1+p_2)-w(p_1))+u(x_3)(1-w(p_1+p_2)) \), pero si por algún motivo el ranking fuera

\( x_2\geq x_3\geq x_1 \) entonces el funcional cambiaría a

\( RDU=u(x_2)w(p_2)+u(x_3)(w(p_2+p_3)-w(p_2))+u(x_1)(1-w(p_2+p_3)) \).

Imagina el trabajo que sería calcular todas las pesos \( g(x_i)=(w(p_1+...+p_i)-w(p_1+...+p_{i-1})) \) si para \( n \) valores de \( x_i \) este orden cambiara \( \displaystyle\frac{n(n-1)}{2}+1 \) veces. Por eso es que digo que calcular todos los \( g(x_i) \) para estas regiones tendría un orden \( O(n^3) \). Tengo que calcular \( n \) valores de \( g(x_i) \) para \( \displaystyle\frac{n(n-1)}{2}+1 \)  regiones.

[Luis Fuentes]

Hola

A ver, dime detallando paso a paso y el tiempo de complejidad que harias tu para hallar ese máximo. Tienes que tener cuidado, que los \( g(x_i) \) dependen de la probabilidad de los \( x_i \) y de su ranking (posición).

Pues no se si sería mejor que volvieses a plantear las condiciones del cálculo de la manera más clara, exacta y precisa posible. En principio el conteo de operaciones lo hice en mi primer mensaje.

Y si el problema es ordenar los \( x_i \) según he entendido SÓLO hay que ordenarlos una vez, lo que supone \( O(n\cdot log(n)) \).

Lo de las regiones sigo sin entenderlo.

Saludos.

[Quema]

Capaz que con un ejemplo me explique mejor. Sea una variable aleatoria \( Y(h) \) que toma cuatro valores \( y_1(h)=10-h,y_2(h)=9-h/2,y_3(h)=1+h \) y \( y_4(h)=2+h/2 \) con probabilidades respectivas \( p_1,p_2,p_3 \) y \( p_4 \), siendo \( h \) un parámetro \( h\in [0, 10] \).

Defino el funcional de esta forma, si \( y_1\geq y_2\geq y_3\geq y_4 \) entonces

\( RDU(Y)=u(y_1)w(p_1)+u(y_2)(w(p_1+p_2)-w(p_1))+u(y_3)(w(p_1+p_2+p_3)-w(p_1+p_2))+u(y_4)(1-w(p_1+p_2+p_3)) \).

Notemos que para aplicar ese funcional los valores de \( Y(h) \) tienen que estar ordenados de forma decreciente. Por ejemplo, si \( h=5 \)


\( y_2(5)>y_3(5)>y_1(5)>y_4(5) \) entonces el funcional pasa a ser

\( RDU(Y(h=5))=u(y_2)w(p_2)+u(y_3)(w(p_2+p_3)-w(p_2))+u(y_1)(w(p_1+p_2+p_3)-w(p_3+p_2))+u(y_4)(1-w(p_1+p_2+p_3)) \), pero para otros valores de \( h \) ese orden varía, y hay que respetar el funcional, asociando las probabilidades del valor mayor hacia el menor tal cual mostrado más arriba. Es decir si el orden para a ser \( y_4>y_3>y_1>y_2 \) entonces, para esa regiòn de \( h \) donde se cumple ese orden tenemos:

\( RDU(Y(h))=u(y_4)w(p_4)+u(y_3)(w(p_4+p_3)-w(p_4))+u(y_1)(w(p_1+p_4+p_3)-w(p_3+p_4))+u(y_2)(1-w(p_1+p_4+p_3)) \)


Por eso el análisis sobre la regiones que hacen variar el orden de los valores de \( Y(h) \). Hacer todo esto para \( n \) rectas digo que tiene tiempo de complejidad \( O(n^3) \).

Pensé también ingreso \( h \) ordeno los \( y_i \) y calculo los \( w(.)-w(..) \) pero creo que termino siendo un orden grande no se si igual al que digo que es tantas intersecciones multiplicado por \( n \).

[Luis Fuentes]

Hola

Capaz que con un ejemplo me explique mejor. Sea una variable aleatoria \( Y(h) \) que toma cuatro valores \( y_1(h)=10-h,y_2(h)=9-h/2,y_3(h)=1+h \) y \( y_4(h)=2+h/2 \) con probabilidades respectivas \( p_1,p_2,p_3 \) y \( p_4 \), siendo \( h \) un parámetro \( h\in [0, 10] \).

mmmm Vale entonces tienes en realidad \( y_i(h)=x_i+a_i\cdot h \).

Una última duda; si entiendo bien se trata de optimizar un valor que depende de \( h \); entonces no me queda claro si quieres calcular las operaciones fijado \( h \) o las operacioens totales incluidas la optimización; en ese segundo caso, no me queda claro como se pretende optimizar, ¿por fuerza bruta? Es decir calculando una colección de valores de \( h \) y quedándose con el mínimo. Si fuese así para contar operaciones hay que tener en cuenta cuantos valores de \( h \) se calculan.

Saludos.

[Quema]

Pero h no depende de n.

[Luis Fuentes]

Hola

Pero h no depende de n.

¿Y...?Eso no responde a mi pregunta. Lo digo porque si es para un \( h \) concreto, en el fondo da igual como se obtengan los \( y_i \). Son unos números que tienes que ordenar. Nos olvidamos de esas rectas.

Pero si son para todos los \( h \), para cada valor de \( h \) quizá habría que volver a ordenar y es ahí donde cabe diseñar una estrategia óptima, pero para ello hay que tener claro para cuantos y qué valores de \( h \) habrá que trabajar.

Saludos.

[Quema]

A mi ejemplo agregale n-5 rectas con valores de ordenada en el origen entre 0 y y 10, y haz que varíen sus pendientes como quieras de tal forma que sea una maraña de cruces de rectas para los \( h \) entre \( [0,1] \).

Además, todavía no me importa llegar al tema de la optimización. Aún si el primer paso es ingresar el \( h \) tienes automáticamente los \( y_i \), pero no sus pesos (la diferencia de los \( w()-w() \)) y para saber cuál aplica tienes que analizar en cuál región cae, para eso tienes que ver los puntos de cortes de las rectas que son como máximo \( \displaystyle\frac{n(n-1)}{2} \).

Supongo que estàs pensando, ingreso \( h \) entonces ya determino los \( y_i \) y los ordeno (tiempo de complejidad \( O(n \log n) \)), pero y determinar los pesos? En este caso, las rectas se cruzan 6 veces y hay siete regiones y por los tanto siete posibles pesos, pero eso se complica si son \( n \) rectas, ahí tienes que calcular \( \displaystyle\frac{n(n-1)}{2}+1 \) pesos con \( n \) calculos en cada uno, por eso digo que el orden es \( O(n^3) \). Si quisieras hacer un if-else programa es imposible pues creo que tendrías que analizar todas las permutaciones de los \( y_i \) para saber cuál peso usar y sería de orden \( O(n!) \). 

[Luis Fuentes]

Hola

Además, todavía no me importa llegar al tema de la optimización. Aún si el primer paso es ingresar el \( h \) tienes automáticamente los \( y_i \), pero no sus pesos (la diferencia de los \( w()-w() \)) y para saber cuál aplica tienes que analizar en cuál región cae, para eso tienes que ver los puntos de cortes de las rectas que son como máximo \( \displaystyle\frac{n(n-1)}{2} \).

Para un valor concreto de \( h \) no acabo de entender que tienen que ver las regiones de las rectas. Tu ordenas las \( y_i(h) \) en \( O(n\, log(n)) \) y punto.

Entonces por resumir la cuestión.

Suponiendo los \( y_i \) entiendo que hay que calcular:

\( RDU(Y)=\displaystyle\sum_{k=1}^n{}u(y_i)(w(p_1+\ldots+p_i)-w(p_1+\ldots+p_{i-1}) \)

Eso son:

- Calculamos \( a_i=\displaystyle\sum_{k=1}^i{}p_i  \), para \( 1\leq i\leq n \) que son \( n-1 \) operaciones.
- Calculamos \( w_i=w(a_i)-w(a_{i-1} \) que son \( 3(n-1) \) operaciones.
- Calculamos \( u(y_i)w_i \) y sumamos que son \( 2n-1 \) operaciones.

En total \( 6(n-1)+1 \) operaciones. Eso es \( O(n) \).

Si le añadimos el coste de ordenar los \( y_i \) eso sería \( O(n\cdot log(n)) \) (ya que \( O(n\\,log(n))>O(n) \).

Si queremos hacer intervenir distintos valores de [ex]h[/tex] no veo forma de contar operaciones sino ponemos en juego CUANTOS valores de \( h \) queremos calcular. Dices \( m \) valores distintos.

En ese caso si repetimos lo anterior a lo bestia, serían operaciones del orden: \( O(m\cdot n\cdot log(n) \) (*).

Con este punto de vista simplemente para cada valor de \( h \) volvemos a reordenar los \( y_i \). Otra opción sería como dices calcular los \( n(n-1)/2 \) cortes de las rectas que nos dan valores \( h_{ij} \) que indican cuando la recta \( y_i \) supera a la \( y_j \). En ese caso se podría reordenar sólo cuando los valores de \( h \) cruzan esos valores y además sólo con un intercambio de posición entre los índices \( i \) e \( j \).

En ese caso el número de operaciones serían \( O(nlog(n)) \) para la ordenación de los \( y_i \) iniciales. \( O(n(n-1)/2) \) para calcular esas intersecciones; pero habría que ordenarlas son: \( O(n(n-1)lob(n(n-1))=O(n^2log(n)) \) (aquí tengo dudas si esto se puede hacer de manera más óptima).

Y después \( O(m\cdot n) \) operaciones (ya que para cada valor de \( h \) ya no hay que reordenar las \( y_i \) sino cambiar de orden los índices \( h_{ij} \) se hayan sobrepasado al cambiar de \( h \). En total serán en el peor de los casos \( O(n(n-1)/2)=O(n^2) \) cambios.

En fin el coste sería:

\( max(O(m\cdot n),O(n^2log(n)) \)

que es mejor que (*) si \( O(m)>O(n) \).

Saludos.

[Quema]

Estamos cerca. En realidad \( h \) puede ser cualquier real entre, en mi ejemplo, \( [0,10] \). Es decir, creo, que tu \( m \) es infinito, por eso pensé siempre en analizar las rectas y las regiones de \( h \) que se determinan, eso lleva, en el peor de los casos tenemos \( \displaystyle\frac{n(n-1)}{2}+1 \) regiones, pero una vez dentro de la región tengo que hallar los pesos que son \( n \) operaciones, por eso digo que es de \( O(n^3) \). En resumen, si \( h \) puede tomar infinitos valores tu primer método como que no es muy viable, no? Tu segundo mètodo, sería para el caso que \( h \) fuera continua, no? Si es así, a mi me da el orden que puse, a vos otro. En este caso, ese sería el método más eficiente?