[pyar] Ejercicio (para entretenerse)

[fisa]

El día 13 de enero de 2012 17:48, fisa <fisadev en gmail.com> escribió:
> 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 -_-
>>

(estoy con la cabeza quemada, hablando demasiado sin pensar. Me releo
y me da vergüenza -_-)


-- 
fisa  -  Juan Pedro Fisanotti