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

Dados 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;
 }
}

1. Determinar qué orden de complejidad presenta cada uno de los dos algoritmos; luego indicar:
   1. Si el array está ordenado, ¿qué algoritmo de búsqueda convendría utilizar?
   2. 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 $\Theta (nlog(n))$):
      1. Ordenarlo primero, y después aplicar búsqueda binaria.
      2. No ordenarlo, y aplicar búsqueda lineal.
2. Comparar el tiempo en el cual cada algoritmo encuentra:
   1. El primer elemento de un array de n elementos.
   2. El elemento de la mitad del array.
3. Identificar el mejor caso, el peor caso y el caso medio de cada uno de los algoritmos.

Solución

Ejercicio 2

La ecuación $A^{5}+B^{5}+C^{5}+D^{5}+E^{5}=F^{5}$ tiene exactamente una solución entera que satisface $0<A\leq B\leq C\leq D\leq E\leq F\leq 75$. Escribir un programa para encontrar dicha solución tomando como sugerencia, calcular primero todos los valores $X^{5}$ y almacenarlos en un vector. Analizar complejidad. Solución

Ejercicio 3

Un 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:

1. Lineal
2. $O(NlogN)$
3. Cuadrático
4. Cúbico

Solución

Ejercicio 4

Un 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:

1. Lineal
2. $O(NlogN)$
3. Cuadrático
4. Cúbico

Solución

Ejercicio 5

Un elemento mayoritario en un vector A de tamaño $N$ es un elemento que aparece más de ${\frac {N}{2}}$ 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

Mostrar que $3*(n+1)^{7}+2n\log n$ es $O(n^{7})$

Solución