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 12: | Línea 12: | ||
* d) Si un enunciado dice "Siempre que vale A sucede inmediatamente B y B no puede suceder de ninguna otra manera" y la correspondiente axiomatización incluye las operaciones A y B entonces el TAD está mal escrito. | * d) Si un enunciado dice "Siempre que vale A sucede inmediatamente B y B no puede suceder de ninguna otra manera" y la correspondiente axiomatización incluye las operaciones A y B entonces el TAD está mal escrito. | ||
== Ejercicio 2 == | == Ejercicio 2 == | ||
Línea 30: | Línea 21: | ||
=== Soluciones === | === Soluciones === | ||
a) | a) Se me ocurre usar un Selection Sort, que seleccione siempre el mayor, y que vaya calculando la suma de los ya seleccionados. Si la cantidad de seleccionados es menor o igual a k, y la suma pasa X, se deja de correr el algoritmo. Esto tendría complejidad <math>O(n^2)</math> en el peor caso, y <math>O(k)</math> en el mejor. Si a alguien se le ocurre alguno mejor, edite esto. | ||
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. | ||
Línea 44: | Línea 35: | ||
* b) Sean S[i] y S[j] claves del heap / i < j y S[i] > S[j] → el arreglo obtenido al intercambiar S[i] y S[j] sigue siendo max-heap. | * b) Sean S[i] y S[j] claves del heap / i < j y S[i] > S[j] → el arreglo obtenido al intercambiar S[i] y S[j] sigue siendo max-heap. | ||
== Ejercicio 4 == | == Ejercicio 4 == |