Hola
No entendí la parte donde si \( n \) puede tomar \( m \) valores el tiempo de complejidad de un método de fuerza bruta es \( A=O(m n \log n) \), si puedes explicarlo de nuevo.
Indica exactamente qué punto no entiendes:
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) \) (*).
Además, eso halla el óptimo de \( RDU(Y(h)) \).
¿Afirmas o preguntas? Lo de calcular el óptimo es casi una cuestión aparte. Es algo que no tengo claro. Tendría que ver que dice la literatura sobre optimización númerica, es algo que no tengo fresco. Desde luego si queremos hallar el máximo de una función \( f(h) \) con \( h\in [a,b] \), sobre la cual
no sabemos NADA, más allá que poder evaluarla en cualquier valor \( h \) no se me ocurre otra forma de hacerlo que no sea por fuerza bruta, es decir, calcular \( m \) valores equidistribuidos en \( [a,b] \) y ver donde \( f(h) \) es mayor.
Así que por ahora es el método que estoy considerando. Sin embargo, sospecho sin embargo que raramente será así. Información extra sobre la función \( f(h) \) cambia el panorama. Como caso extremo si \( f(h) \) es creciente el máximo está en \( f(b) \) y es inmediato. Si es cóncava, el máximo es único y se puede hacer un algoritmo mucho más óptimo parecido al de la bisección.
El otro método que usa los puntos de intersección tampoco entendí cómo llegar a \( B=\max\{O(mn), O(n^2 \log n)\} \) si puedes explicarlo mejor.
Lo mismo; intenta precisar la duda:
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)) \)
De nuevo, eso halla el valor óptimo de \( h \)?
Sobre esto lo mismo; lo halla por fuerza brutísima.
Además, si \( m\geq n \log n \) entonces \( A<B \) y en caso contrario hay que ver si \( m<n \) entonces \( A<B \) y en caso contrario \( A>B \), no?
Si tienes \( A=O(mnlog(n)) \) y \( B=max(O(m\cdot n),O(n^2log(n)) \):
- Si \( m\leq n \) entonces \( mnlog(n)\geq mn[tex] y [tex]mnlog(n)\geq n^2log(n) \) y por tanto \( A\geq B \).
- Si \( m<n \) entonces \( mnlog(n)<n^2log(n) \) y por tanto \( A\leq O(n^2log(n))\leq B \).
Saludos.
