1
Computación e Informática / Re: Tiempo complejidad
« en: Hoy a las 06:23 pm »
Hola
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.
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.