Hola
No entiendo cuando pones:
a) 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.
¿De dónde sale el 3, no debería ser \( n(n-1) \)
El tres sale de, para cada \( i \) evaluar \( w(a_i) \) (1), evaluar \( w(a_{i-1}) \) (2) y restar (3) (ahí están las \( 3 \) operaciones).
Por otro lado no tienes que multiplicar \( n \) por \( n-1 \). Ten en cuenta que los \( a_i \) se calculan una sola vez. \( a_1=p_1 \), \( a_2=a_1+p_2 \), \( a_3=a_2+p_3 \), \( a_4=a_3+p_4 \). En total \( n-1 \) operaciones.
Y luego para cada \( i \) calcular \( u(y_i)(w(a_i)-w(a_{i-1}) \) que son \( 5 \) operaciones (tres evaluaciones de funciones, una resta y un producto). Como \( i \) va de \( 1 \) a \( n \) serían \( 5n \) (yo puse \( 5(n-1) \) pero es lo de menos; está el detallito de que cuando \( i=1 \) no se resta nada).
Entonces la cosa es que es todo de orden \( O(n) \) (los coeficientes 5,6,... es lo de menos).
Para entender bien esto voy a empezar a calcular los ordenes a ver que me digas en qué parte le estoy errando.
a) El A, tomo un valor determinado de \( h \) ordeno los \( y_i \) tiene un orden \( O(n \log n) \).
Bien.
Ahora tengo que calcular los \( w(p_1+...+p_j)-w(p_1+...+p_{j-1}) \). El primero es \( w(p_1) \), el segundo \( w(p_1+p_2)-w(p_1) \), el tercero \( w(p_1+p_2+p_3)-w(p_1+p_2) \),...y el último \( 1-w(p_1+p_2+...+p_{n-1}) \) es como \( 1+2+...+n=\displaystyle\frac{n(n-1)}{2} \) entonces es de orden \( O(n^2). \)
No; eso no lo estás haciendo de manera óptima. Las sumas \( p_1+p_2+p_3+\ldots \) no tienes que calcularlas repetidas de cada vez.
Como te indiqué antes las haces una sola vez \( a_k=p_1+p_2+\ldots+p_k \); o más en concreto \( a_1=p_1 \) y \( a_{k+1}=a_k+p_{k+1} \). Esto sólo son \( n-1 \) operaciones.
Por tanto eso que a ti te da \( O(n^2) \) se puede hacer en \( O(n) \).
El resto es de orden \( O(n) \), entonces el orden para los \( m \), \( h \), entonces hallar el máximo \( O(m n \log n) \). Hay algo mal?
Aquí estamos de acuerdo. De hecho no has usado el \( O(n^2) \) que decías antes.
b) No me queda claro en \( B \), un orden, por qué queda \( O(n^2 \log n) \) y no aparece el \( m \), no debería ser \( O(m n^2 \log n) \) .
Ese \( O(n^2 \log n) \) viene del coste de intersecar todas las rectas \( y_i(h) \) y ordenar los \( n(n-1)/2 \) puntos de corte \( h_{ij} \). Esto no depende de ningún valor concreto de \( h \); es decir no es una cosa que haya que \( m \) veces, supuesto que queremos hallar el valor de \( RDU \) para \( m \) valores de \( h \). Se hace una vez independientemente de que \( m=1 \) ó \( m=10^9 \).
Yo creo que sería así, hallar los puntos de intersección tiene orden \( O(n^2) \), ordenarlos tiene orden \( O(n^2 \log n^2) \) (tu aquí pones \( O(n^2\log n) \)).
Porque \( log(n^2)=2log(n) \) y entonces:
\( O(n^2log(n^2))=O(2n^2log(n))=O(n^2log(n)) \)
Ahora calcular los pesos de cada sección es \( O(n^2) \), como hay \( \displaystyle\frac{n(n-1)}{2} \) regiones el orden de calcular todos los pesos de \( O(n^4) \).
En lo de calcular los pesos de cada sección, estas volviendo a usar \( O(n^2) \) cuando puede hacerse en \( O(n) \).
Pero la idea ahora sería la siguiente. Queremos calcular el valor de \( RDU(h) \), para \( m \) valores de \( h \). Tenemos previamente calculados intervalos \( [h_i,h_{i+1}) \) en los cuales sabemos que el orden de los \( y_i(h) \) no varía.
Entonces para el primer valor de \( h\in [h_1,h_2) \) sabemos el orden de los \( y_i(h) \) o en todo caso los reordenamos y serían \( O(nlog(n))<O(n^2log(n)) \). La clave es que esta ordenación sólo se hará para el primer \( h \). Después calculamos \( RDU(h) \) en \( O(n) \) operaciones.
Ahora para los siguientes valores de \( h\in [h_1,h_2) \) no hay nada que reordenar. Por tanto seguimos teniendo \( O(n) \) operaciones para calcular \( RDU(h) \).
Si \( h \) "salta" de \( [h_1,h_2) \) a \( [h_2,h_3) \) ahí sabemos que una recta \( y_i \) ha pasado a otra \( y_j \) entonces intercambiamos el orden de ambas; y de nuevo para calcular \( RDU(h) \) necesitamos \( O(n) \) operaciones.
En resumen, si calculamos \( m \) valores de \( h \) necesitamos \( O(mn) \) operaciones.
La diferencia entre \( A \) y \( B \) es en definitiva que en \( A \) para cada \( h \) reordenamos los \( y_i(h) \) "partiendo de cero". Mientras en en \( B \) gastamos primero \( O(n^2log(n)) \) operaciones en intersecar las rectas y obtener los puntos de intersección; a cambio para cada valor de \( h \) ya no tenemos que volver a reordenar los \( y_i(h) \).
c) Por otro lado en C, el orden de complejidad para un solo valor de \( h \) debería ser siendo \( O(n \log n) \) pues simplemente sabemos, por construcción, que hay elementos repetidos. No tiene sentido que sea \( O( t \log t) \). En todo caso deberíamos compararlo con el orden de hallar el MCM que es, creo, \( O( n \log \max (b_1,b_2,...,b_n)) \) siendo los \( b_i \) los denominadores de la probabilidades individuales.
Si; en eso estoy de acuerdo. En realidad basta ordenar los \( n \) ya que el salto a \( t \) valores únicamente supone repetir algunos cierto número de veces.
Saludos.
