Comparación de modelos

Dos formas de contar palabras

Para las 100 palabras más frecuentes de un libro de 500 000 palabras (30 000 distintas):

A: contar con una tabla hash y ordenar las 30 000 por frecuencia.
B: contar con una tabla hash y pasar las 30 000 por un heap de tamaño 100.

Para las 100 palabras más frecuentes de un libro de 500 000 palabras (30 000 distintas): A cuenta con una tabla hash y ordena las 30 000 por frecuencia; B cuenta con una tabla hash y pasa las 30 000 por un heap de tamaño 100. ¿Qué diferencia hay entre A y B?B no sirve: un heap de tamaño 100 no puede garantizar los 100 mayores entre 30 000 palabras distintasContar cuesta igual; A ordena en O(u log u) y B selecciona en O(u log 100). B hace menos, pero ambas son rápidasA es O(n²), porque ordenar todas las palabras distintas cuesta cuadrático con 30 000 palabras en un libroSon equivalentes: ordenar todo y quedarse con 100 hace el mismo trabajo que mantener un heap de 100 elementos