Manual del estudiante de Ingeniería en Sistemas de UTN/Diseño e Implementación de Estructuras de Datos/Guías prácticas/Complejidad computacional
Ejercicio 1
editarDados los siguientes códigos de búsqueda:
public class Buscar { public static boolean buscar(int numero, int[] array) { int i; for (i=0; i < array.length; i++) if (numero == array[i]) return true; return false; } }
public class BuscadorBinario { public static boolean buscar(int numero, int[] array) { int a = 0; // extremo inf del rango int z = array.length - 1; // extremo sup del rango int m; // medio del rango while (a <= z) { // inicia en un sitio aleatorio: el medio del rango? m = (a + z) / 2; if (array[m] == numero) return true; // cortamos el rango en dos if (array[m] < numero) a = m + 1; else z = m - 1; } return false; } }
- Determinar qué orden de complejidad presenta cada uno de los dos algoritmos; luego indicar:
- Si el array está ordenado, ¿qué algoritmo de búsqueda convendría utilizar?
- Si el array no está ordenado, ¿qué harías? (Quicksort es el algoritmo de ordenación más rápido conocido, y su complejidad promedio es ):
- Ordenarlo primero, y después aplicar búsqueda binaria.
- No ordenarlo, y aplicar búsqueda lineal.
- Comparar el tiempo en el cual cada algoritmo encuentra:
- El primer elemento de un array de n elementos.
- El elemento de la mitad del array.
- Identificar el mejor caso, el peor caso y el caso medio de cada uno de los algoritmos.
Ejercicio 2
editarLa ecuación tiene exactamente una solución entera que satisface . Escribir un programa para encontrar dicha solución tomando como sugerencia, calcular primero todos los valores y almacenarlos en un vector. Analizar complejidad. Solución
Ejercicio 3
editarUn algoritmo tarda 0,5 milisegundos para una entrada de tamaño 100. Determinar cuánto tardará con una entrada de 500 si el tiempo de ejecución es el siguiente:
- Lineal
- Cuadrático
- Cúbico
Ejercicio 4
editarUn algoritmo tarda 0,5 milisegundos para una entrada de tamaño 100. Determine qué tamaño puede procesar en un minuto , si el tiempo de ejecución es:
- Lineal
- Cuadrático
- Cúbico
Ejercicio 5
editarUn elemento mayoritario en un vector A de tamaño es un elemento que aparece más de veces ( en consecuencia habrá a lo sumo uno). Por ejemplo:
- [ 3, 3, 4, 2, 4, 4, 2, 4, 4] un elemento mayoritario es 4
- [ 3, 3, 4, 2, 4, 4, 2, 4] no tiene mayoritario
Escriba un algoritmo para encontrar el elemento mayoritario cuando exista ,o que diga que no existe. Indique cuál es el tiempo de ejecución del algoritmo. Solución
Ejercicio 6
editarMostrar que es