Algoritmos y Estructuras de Datos (VJ1215)

Sin ordenar el vector, podemos resolver el problema con este algoritmo en tiempo O(n²), siendo n la talla del vector:

	
void diferenciaMinimaLenta(const vector<float> & v) {
   
   float minimo = numeric_limits<float>::infinity();

   float candidato, primero, segundo;

   for (int i = 0; i <= v.size() - 2; i++)
      for (int j = i + 1; j <= v.size() - 1; j++) {
	 candidato = abs(v[i] - v[j]);
	 if (candidato < minimo) {
	    minimo = candidato;
	    primero = v[i];
	    segundo = v[j];
	 }
      }
   
   cout << "Resultado: " << primero << ", " << segundo << endl;
   
}
      

Esta solución ilustra también cómo podemos utilizar infinito en C++. Puedes ver tambén este ejemplo_infinity.cpp

Una solución diferente consiste en ordenar primero el vector y después aprovechar que, al estar ordenado, los dos elementos buscados estarán en posiciones contiguas del vector.

Para ordenar un vector eficientemente en C++, con coste temporal O(n log n) en el peor caso, podemos utilzar la función sort como ilustra este ejemplo_sort.cpp

Si, por cualquier motivo, no pudiésemos modificar el vector original, bastaría hacer una copia y ordenar la copia. A continuación se muestran dos formas de hacer esa copia: utilizando un constructor de copia, o pasando el vector por valor. De ambas formas, el coste temporal de copiar el vector es O(n).

	
void diferenciaMinimaRapida(const vector<float> & v) { // O(1), por referencia
   
   float minimo = numeric_limits<float>::infinity();

   float candidato, primero, segundo;

   vector<float> copia(v); // O(n), constructor de copia

   sort(copia.begin(), copia.end()); // O(n log n)

   for (int i = 0; i <= copia.size() - 2; i++) { // O(n)
      candidato = copia[i + 1] - copia[i];
      if (candidato < minimo) {
	 minimo = candidato;
	 primero = copia[i];
	 segundo = copia[i + 1];
      }
   }
   cout << "Resultado: " << primero << ", " << segundo << endl;
   
}
      

	
void diferenciaMinimaRapida(vector<float> v) { // O(n), por valor
   
   float minimo = numeric_limits<float>::infinity();

   float candidato, primero, segundo;

   sort(v.begin(), v.end()); // O(n log n)

   for (int i = 0; i <= v.size() - 2; i++) { // O(n)
      candidato = v[i + 1] - v[i];
      if (candidato < minimo) {
	 minimo = candidato;
	 primero = v[i];
	 segundo = v[i + 1];
      }
   }
   cout << "Resultado: " << primero << ", " << segundo << endl;
   
}
      

El coste de esta solución depende del coste de la ordenación. Si empleásemos un algoritmo que ordenase en tiempo O(n²), el coste total sería O(n + n² + n) = O(n²), que no mejora el coste de la primera solución. Pero si empleamos un algoritmo que ordene en tiempo O(n log n), que es lo que hace sort en C++, el coste total es O(n + n log n + n) = O(n log n), mejor que el del primer algoritmo. Por tanto, para resolver este problema vale la pena realizar una ordenación en tiempo O(n log n), no vale la pena hacerlo en tiempo O(n²).

Código de prueba