[pyar] Buscar máximo

[Angel Java Lopez]

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))?



2014/1/17 Alejandro Santos <listas en alejolp.com>

> Asi en el aire mas o menos te digo que la busqueda ternaria es
> O(log(n)) y tu segunda solucion es O(n log(n)).
>
> La segunda forma que conozco es también O(log(n)), pero mucho más
> matemática, y hasta ligeramente tramposa ;)
>
> 2014/1/17 Angel Java Lopez <ajlopez2000 en gmail.com>:
> > Bien, otra idea
> >
> > Tengamos un intervalo inicial [a, b]
> >
> > Ponemos n puntos en el medio: x1, x2, .... xn, distintos entre si, en
> orden
> > creciente, distintos de a y b.
> >
> > Por cada vez que
> >
> > f(x(i)) < f(x(i+1)) < f(x(i+2))
> >
> > destartamos todo el segmento a la izquierda de x(i+1)
> >
> > Cada vez que
> >
> > f(x(i)) > f(x(i+1)) > f(x(i+2))
> >
> > descartamos todo a la derecha de x(i+1)
> >
> > Nos queda un segmento. Repetimos el proceso
> >
> > Cuanto mayor sea n, mas cuesta, pero tambien mas rapido llegamos a estar
> > cerca del maximo.
> >
> > Si miramos fijo lo de arriba, queda que hay una sola terna consecutiva
> que
> > no es monotona creciente o decreciente. Los extremos de esa terna, son el
> > nuevo intervalo.
> >
> > Hmmm... no se porque, me suena que estaba en Programming Pearls el
> problema
> >
> > Nos leemos!
> >
> > Angel "Java" Lopez
> > @ajlopez
> >
> >
> >
> > On Fri, Jan 17, 2014 at 7:54 PM, Alejandro Santos <listas en alejolp.com>
> > wrote:
> >>
> >> 2014/1/17 Alejandro Santos <listas en alejolp.com>:
> >> > 2014/1/17 david weil <tenuki en gmail.com>:
> >> >>
> >> >> No entiendo.. de donde se dedujo que la función es monótona?
> >> >>
> >> >
> >> > De ningun lado. El problema original estaba incompleto.
> >> >
> >>
> >> De todas formas f no es monotona en [a,b]. Si es monotona en [a, x] y
> [x,
> >> b].
> >>
> >> --
> >> 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/acf9ba3f/attachment.html>