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

editar

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

editar

La 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

editar

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.  
  3. Cuadrático
  4. Cúbico

Solución

Ejercicio 4

editar

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.  
  3. Cuadrático
  4. Cúbico

Solución

Ejercicio 5

editar

Un 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

editar

Mostrar que   es  

Solución