[pyar] Ejercicio (para entretenerse)

[Luis Masuelli]

Un hashing sobre un histograma de las letras de cada palabra... Ineficiente en espacio pero seria O(n). Cabe destacar que como la entrada es variable, n es letras y no palabras en cualquier caso

> From: fisadev en gmail.com
> Date: Fri, 13 Jan 2012 17:48:28 -0300
> To: pyar en python.org.ar
> Subject: Re: [pyar] Ejercicio (para entretenerse)
> 
> El día 13 de enero de 2012 17:45, fisa <fisadev en gmail.com> escribió:
> > El día 13 de enero de 2012 17:41, Lucio Torre <lucio.torre en gmail.com> escribió:
> >> 2012/1/13 fisa <fisadev en gmail.com>:
> >>> El día 13 de enero de 2012 15:56, Tordek <kedrot en gmail.com> escribió:
> >>>> On 13/01/12 15:14, fisa wrote:
> >>>>>
> >>>>> El día 13 de enero de 2012 14:31, fisa<fisadev en gmail.com>  escribió:
> >>>>
> >>>>
> >>>>> Aclaro que no usé ningún tipo se sort (y eso hizo que el código sea
> >>>>> bastante más feo) para que sea O(N), ya que un sort de cualquier tipo
> >>>>> sería peor que O(N).
> >>>>
> >>>>
> >>>> Tu algoritmo es O(N*k) (si get y set son O(1)), mientras este es O(N*k lg
> >>>> k), donde k es la longitud de la palabra.
> >>>
> >>> Me expresé bastante mal.
> >>> Debería haber dicho "para que sea con O de crecimiento lineal", no
> >>> "para que sea O(N)".
> >>> Perdón, escribí apurado.
> >>
> >> Bueno, tambien se podria decir que no hay palabras de mas de 1000
> >> letras entonces lo podemos poner como una constante, y aun si hay un
> >> sort *sobre las letras de una palabra*, sigue siendo O(N).
> >>
> >> Lucio.
> >
> > Sep, es verdad.
> > Por un lado que todo esto es hablando de k como un valor máximo de
> > peor caso, para que sea constante. Porque si no lo fuese, N*k no es
> > algo lineal, y estamos hablando de un O en base a dos valores
> > variables, cosa que no existe (es un plano..)
> 
> Existe en realidad, pero no tiene mucho sentido para analizar el
> comportamiento del algoritmo respecto a N (cantidad de palabras), que
> es lo que importa en este caso.
> 
> > Y por otra parte, que si k entonces es constante, también se considera
> > trivial y constante el ordenamiento de las letras por cada palabra,
> > así que se puede considerar como un O(N) usando los sorts de esa
> > manera.
> > Ergo, al pedo la compliqué para no usar sorts en las letras de cada palabra -_-
> >
> > --
> > fisa  -  Juan Pedro Fisanotti
> 
> 
> 
> -- 
> 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
 		 	   		  
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://listas.python.org.ar/pipermail/pyar/attachments/20120113/12122455/attachment.html>