[pyar] Buscar máximo

[Angel Java Lopez]

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
>
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://listas.python.org.ar/pipermail/pyar/attachments/20140117/bd3e81dc/attachment.html>