Algoritmos
Publicado por Sandra (1 intervención) el 15/08/2007 11:10:45
Hola.
Tengo serios problemas con algoritmos y quiciera un poco de ayuda.
1) Suponiendo que existen n números en binario, cada uno con k digitos. Probar que se pueden ordenar en O(kn).
2) Si deseamos ordenar n enteros cuyos valores están entre uno y n^2. Probar que esto se puede hacer en tiempo lineal.
3) Dado un arreglo A de n números, ¿hay algún elemento de A que aparezca al menos n/3 veces?. Encontrar un algoritmo lineal para resolver este problema.
4) ¿Cuántas comparaciones son necesarias para ordenar una lista de 9 elementos?. Justificar su respuesta.
5) Dada una lista de n enteros {x1, ..., xn} y un número y, encontrar un algoritmos que en O(n ln n)$ encuentre la pareja (i, j) tal que x1 + xj <= y tal que maximice xi+xj.
Gracias por su ayuda y si teneis tips para aprender a obtener conocimientos al respecto os agradeceria.
Tengo serios problemas con algoritmos y quiciera un poco de ayuda.
1) Suponiendo que existen n números en binario, cada uno con k digitos. Probar que se pueden ordenar en O(kn).
2) Si deseamos ordenar n enteros cuyos valores están entre uno y n^2. Probar que esto se puede hacer en tiempo lineal.
3) Dado un arreglo A de n números, ¿hay algún elemento de A que aparezca al menos n/3 veces?. Encontrar un algoritmo lineal para resolver este problema.
4) ¿Cuántas comparaciones son necesarias para ordenar una lista de 9 elementos?. Justificar su respuesta.
5) Dada una lista de n enteros {x1, ..., xn} y un número y, encontrar un algoritmos que en O(n ln n)$ encuentre la pareja (i, j) tal que x1 + xj <= y tal que maximice xi+xj.
Gracias por su ayuda y si teneis tips para aprender a obtener conocimientos al respecto os agradeceria.
Valora esta pregunta
0