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/Solución al ejercicio 5 de complejidad computacional

De Wikilibros, la colección de libros de texto de contenido libre.

Antes de escribir el algoritmo, voy a evaluar posibles soluciones:

  • Contabilizar la aparición de cada elemento, asistido por una estructura que devuelva la posición donde guardar el dato en el menor tiempo posible.
  • Ordenar el vector y resolver el problema en una sola pasada.

Para la primera opción, debe seleccionarse una estructura de datos índice. La mejor posibilidad en este caso podría ser una tabla de dispersión, pero la complejidad de las operaciones depende mucho de la entrada, de manera que es difícil de evaluar, especialmente para un algoritmo genérico tal como el del problema[1]; por esa razón, para evaluar esta posibilidad, elijo un árbol de búsqueda, cuya complejidad para inserción y acceso es de . Por cada elemento, debe guardarse su entrada, o incrementarse en caso de estar ya presente, compararse con la máxima, y guardarse como la máxima si fuere el caso. Este procedimiento costaría un tiempo de .

La segunda opción, si utilizáramos el algoritmo “Heap Sort”, nos tomaría un tiempo de en el peor de los casos[2]. Por ser la alternativa más simple, es la que seleccionaré para resolver el problema. La desventaja que presenta es que es menos general: requerirá que los objetos del vector implementen la interface comparable.

public static Object elementoComparableMayoritario(Vector elementos)
{
 HeapSort.heapSort(elementos);
 Object mayoritario=elementos.elementAt(0);
 int cantidad=1;
 for(int i=1;i<elementos.size();i++)
 {
   if(mayoritario.equals(elementos.elementAt(i))) cantidad++;
   else
   {
     if (cantidad>elementos.size()/2) return mayoritario;
     mayoritario=elementos.elementAt(i);
     cantidad=1;
   }
 }
 if (cantidad>elementos.size()/2) return mayoritario;
 else return null;
}

^ Si se asume que la complejidad de acceso e inserción es constante, esta sería la mejor opción.

^ Para el caso promedio, con datos distribuidos en forma uniforme Quick Sort suele tener mejor desempeño, pero en el peor de los casos su complejidad es de .