Algoritmos y Estructuras de Datos (VJ1215)

Supondremos a continuación que no podemos modificar los vectores dados. Por ello, hacemos copias.

bool mismosDatos(const vector<float> & v1, const vector<float> & v2) { // O(1)

   if (v1.size() != v2.size()) // Esto se puede quitar si estamos seguros de que son de la misma talla
      return false;

   vector<float> copia1(v1), // O(n)
                 copia2(v2); // O(n)

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

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

   for (int i = 0; i < copia1.size(); i++) // O(n)
      if (copia1[i] != copia2[i])
	 return false;
   return true;   

}
      

Código de prueba

El coste temporal de la solución anterior en el peor caso es O(n + n + n log n + n log n + n) = O(n log n), siendo n la talla de ambos vectores.

Alternativamente, para no modificar los vectores originales podríamos pasar los vectores por valor. En ese caso pagaríamos el tiempo de la copia en el momento de la llamada, incluso si fuesen de tallas diferentes.

Si pudiésemos modificar los vectores originales, nos ahorraríamos el tiempo de hacer las copias pero el coste temporal total seguiría siendo O(n log n):

bool mismosDatos(vector<float> & v1, vector<float> & v2) { // O(1)

   if (v1.size() != v2.size())
      return false;

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

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

   for (int i = 0; i < v1.size(); i++) // O(n)
      if (v1[i] != v2[i])
	 return false;
   return true;   

}