[pyar] Buscar máximo

[fisa]

Lo bueno es que dado un valor de precisión constante, el tiempo de
cálculo es lineal respecto al tamaño del rango.
Y a la vez, dado un rango constante, el tiempo de cálculo es lineal
respecto al valor de precisión.

El día 17 de enero de 2014, 20:36, fisa <fisadev en gmail.com> escribió:
> Está bien ubicado en ese punto, porque el corte del bucle es "cuando
> los vecinos de mi x sean peores". O sea, cuando desde tu x mirando
> para izquierda y derecha, en las dos direcciones f baje.
>
> Lo que uno puede hacer para tener mejor o peor precisión es subir o
> bajar el 0.001 que uso.
> Con un número más grande, la precisión baja pero el tiempo de cálculo
> baja. Con un número más chico, la precisión sube pero el tiempo de
> cálculo sube.
>
>
> El día 17 de enero de 2014, 20:33, Angel Java Lopez
> <ajlopez2000 en gmail.com> escribió:
>> Ah!
>>
>> pero esta bien el return? parece que se corta demasiado rapido en algunos
>> casos. Hmmm... yo podria un loop por cantidad de decimales.
>>
>> def hill_climbing():
>>     actual = (a + b) / 2  # medio entre a y b
>>     while True:
>>         mejor_vecino = vecino con f más alto en vecinos(actual)
>>         if f(actual) > f(mejor_vecino):
>>             return actual
>>         else:
>>             actual = mejor_vecino
>>
>> def vecinos(x):
>>     return (x + 0.001, x - 0.001)
>>
>>
>> 2014/1/17 fisa <fisadev en gmail.com>
>>>
>>> Y adelanto el principal problema de hill_climbing (aparte de máximos
>>> locales, que en este caso no tenemos):
>>> Si hay una meseta, se va a quedar estancado en ese punto.
>>>
>>> El día 17 de enero de 2014, 20:27, Angel Java Lopez
>>> <ajlopez2000 en gmail.com> escribió:
>>> > Ah! Ahora entendi, es O(n log(m)) no O(n log(n))
>>> >
>>> > Para mi daba lo mismo, porque
>>> >
>>> > O(n log(m)) en la segunda
>>> > O(2 log(m)) en la primera == O(log(m))
>>> >
>>> > es asi?
>>> >
>>> > Bueno, gracias por el problema, muy bueno, paso a offline, time to fight
>>> > for
>>> > my food ;-)
>>> >
>>> > Angel "Java" Lopez
>>> > @ajlopez
>>> >
>>> >
>>> > 2014/1/17 Alejandro Santos <listas en alejolp.com>
>>> >>
>>> >> La busqueda ternaria es O(log(M)), donde M representa la precisión del
>>> >> resultado en decimales.
>>> >>
>>> >> La busqueda en N subintervalos con el pseudo codigo de recien es O(N
>>> >> log(M)), donde N es la cantidad de subintervalos, y M la precisión del
>>> >> resultado en decimales.
>>> >>
>>> >>
>>> >>
>>> >>
>>> >> 2014/1/17 Angel Java Lopez <ajlopez2000 en gmail.com>:
>>> >> > Bien, mencionas "n de afuera", cual es el "n de adentro"?
>>> >> >
>>> >> > Si no hay "n de afuera" distinto de "n de adentro", veo que las dos
>>> >> > tienen
>>> >> > la misma O
>>> >> >
>>> >> >
>>> >> > 2014/1/17 Alejandro Santos <listas en alejolp.com>
>>> >> >>
>>> >> >> 2014/1/17 Angel Java Lopez <ajlopez2000 en gmail.com>:
>>> >> >> > Hmmm...
>>> >> >> >
>>> >> >> > cual es el n en O(log(n))?
>>> >> >> >
>>> >> >> > Yo puse n en la segunda solucion, a ese n se refiere O(n log(n))?
>>> >> >> >
>>> >> >>
>>> >> >> Ok, capaz hacer un analisis BigOh sin codigo es... confuso.
>>> >> >>
>>> >> >> El n de afuera se refiere a la cantidad de subintervalos en que
>>> >> >> partís
>>> >> >> [a, b], y en que luego partis el subintervalo no monótono.
>>> >> >>
>>> >> >> Con tu explicación me imaginé algo así:
>>> >> >>
>>> >> >> def busqueda_en_intervalos(f, a, b, N):
>>> >> >>     EPS=1e-8
>>> >> >>     while True:
>>> >> >>         L = partir_en_intervalos(f, a, b, N)
>>> >> >>         for E in L:
>>> >> >>             if not es_monotono(E):
>>> >> >>               a, b = E
>>> >> >>               break
>>> >> >>         if abs(a - b) <= EPS:
>>> >> >>             return (a + b) / 2
>>> >> >>
>>> >> >> --
>>> >> >> Alejandro Santos
>>> >> >>
>>> >> >> _______________________________________________
>>> >> >> pyar mailing list pyar en python.org.ar
>>> >> >> http://listas.python.org.ar/listinfo/pyar
>>> >> >>
>>> >> >> PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
>>> >> >>
>>> >> >> La lista de PyAr esta Hosteada en USLA - Usuarios de Software Libre
>>> >> >> de
>>> >> >> Argentina - http://www.usla.org.ar
>>> >> >
>>> >> >
>>> >> >
>>> >> > _______________________________________________
>>> >> > pyar mailing list pyar en python.org.ar
>>> >> > http://listas.python.org.ar/listinfo/pyar
>>> >> >
>>> >> > PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
>>> >> >
>>> >> > La lista de PyAr esta Hosteada en USLA - Usuarios de Software Libre
>>> >> > de
>>> >> > Argentina - http://www.usla.org.ar
>>> >>
>>> >>
>>> >>
>>> >> --
>>> >> Alejandro Santos
>>> >> _______________________________________________
>>> >> pyar mailing list pyar en python.org.ar
>>> >> http://listas.python.org.ar/listinfo/pyar
>>> >>
>>> >> PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
>>> >>
>>> >> La lista de PyAr esta Hosteada en USLA - Usuarios de Software Libre de
>>> >> Argentina - http://www.usla.org.ar
>>> >
>>> >
>>> >
>>> > _______________________________________________
>>> > pyar mailing list pyar en python.org.ar
>>> > http://listas.python.org.ar/listinfo/pyar
>>> >
>>> > PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
>>> >
>>> > La lista de PyAr esta Hosteada en USLA - Usuarios de Software Libre de
>>> > Argentina - http://www.usla.org.ar
>>>
>>>
>>>
>>> --
>>> fisa  -  Juan Pedro Fisanotti
>>> _______________________________________________
>>> pyar mailing list pyar en python.org.ar
>>> http://listas.python.org.ar/listinfo/pyar
>>>
>>> PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
>>>
>>> La lista de PyAr esta Hosteada en USLA - Usuarios de Software Libre de
>>> Argentina - http://www.usla.org.ar
>>
>>
>>
>> _______________________________________________
>> pyar mailing list pyar en python.org.ar
>> http://listas.python.org.ar/listinfo/pyar
>>
>> PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
>>
>> La lista de PyAr esta Hosteada en USLA - Usuarios de Software Libre de
>> Argentina - http://www.usla.org.ar
>
>
>
> --
> fisa  -  Juan Pedro Fisanotti



-- 
fisa  -  Juan Pedro Fisanotti