Edición de «Final 10/03/17 (Algoritmos II)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 30: | Línea 30: | ||
=== Soluciones === | === Soluciones === | ||
a) Hacer max_heapify del arreglo, sumar los k primeros, y en base a eso decidir si ordenar o no. Esto sería <math> O(N | a) Hacer max_heapify del arreglo, sumar los k primeros, y en base a eso decidir si ordenar o no. Esto sería <math> O(N) </math> en el caso que no haya que ordenar, <math> O(N * log(N)) </math> para cuando sí haya que ordenar. | ||
b) Usaría un Heap Sort, ya que permite ordenar el arreglo en <math>O(n*log(n))</math>, y la inserción cuesta solamente <math>O(log(n))</math>. No se me ocurre un método mejor. | b) Usaría un Heap Sort, ya que permite ordenar el arreglo en <math>O(n*log(n))</math>, y la inserción cuesta solamente <math>O(log(n))</math>. No se me ocurre un método mejor. |