[pyar] Ejercicio (para entretenerse)

[fisa]

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