[pyar] Ejercicio (para entretenerse)

[fisa]

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