[pyar] Buscar máximo

[Alejandro Santos]

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