X-Git-Url: https://git.llucax.com/z.facultad/75.29/susanita.git/blobdiff_plain/9544fcaa595b6a6f14b86768429c1883fa39ec6d..7c555835b280bcbc38f170ba3b0afc33b1be43c7:/src/galeshapley.cpp

diff --git a/src/galeshapley.cpp b/src/galeshapley.cpp
index 494631c..5667dfe 100644
--- a/src/galeshapley.cpp
+++ b/src/galeshapley.cpp
@@ -14,7 +14,7 @@ GaleShapley(size_type capacidad):
 
 void
 GaleShapley::
-primera_ronda() // O(N^2.log(N))
+primera_ronda() // O(N^2)
 {
 	cant_comprometidos = 0;
 	for (personas_type::iterator ih = hombres.begin(); // O(N)
@@ -22,23 +22,23 @@ primera_ronda() // O(N^2.log(N))
 	{
 		(*ih)->declarar_a(*((*ih)->prefs.front())); // O(1)
 	}
+
+	// En total es O(N)*(O(N) + O(log(N))) = O(N^2)
 	for (personas_type::iterator im = mujeres.begin(); // O(N)
 			im != mujeres.end(); ++im)
 	{
 		Persona& m = **im;
 		if (m.ofertas.empty()) // O(1)
 			continue;
-		m.ordenar_ofertas(); // O(N.log(N))
-		Persona& prometido = *(m.ofertas.front()); // O(1)
-		m.ofertas.pop_front(); // O(1)
-		m.comprometer_con(prometido); // O(N)
+		Persona* prometido = m.pop_oferta(); // O(log(N))
+		m.comprometer_con(*prometido); // O(N)
 		cant_comprometidos++;
 	}
 }
 
 void
 GaleShapley::
-nesima_ronda() // O(N^2.log(N))
+nesima_ronda() // O(N^2)
 {
 	// Todo el for es O(N^2)
 	for (personas_type::iterator ih = hombres.begin(); // O(N)
@@ -63,7 +63,7 @@ nesima_ronda() // O(N^2.log(N))
 		h.declarar_a(*pm); // O(1)
 	}
 
-	// Todo el for es O(N^2.log(N))
+	// Todo el for es O(N^2)
 	for (personas_type::iterator im = mujeres.begin(); // O(N)
 			im != mujeres.end(); ++im)
 	{
@@ -71,9 +71,7 @@ nesima_ronda() // O(N^2.log(N))
 		if (m.ofertas.empty()) // O(1)
 			continue;
 
-		m.ordenar_ofertas(); // O(N.log(N))
-		Persona* ph = m.ofertas.front(); // O(1)
-		m.ofertas.pop_front(); // O(1)
+		Persona* ph = m.pop_oferta(); // O(log(N))
 		if (m.estado == Persona::COMPROMETIDO)
 		{
 			if (m.cmp(*(m.pareja), *ph) < 0) // O(1)
@@ -91,7 +89,7 @@ nesima_ronda() // O(N^2.log(N))
 				for (Persona::ofertas_type::iterator i // O(N)
 						= m.ofertas.begin();
 						i != m.ofertas.end(); ++i)
-					(*i)->rechazos[(&m)->nombre] = &m;
+					(*i)->rechazos[(&m)->nombre] = &m;//O(1)
 
 				ph->rechazos[(&m)->nombre] = &m;
 				m.ofertas.clear(); // O(N)
@@ -118,10 +116,13 @@ todos_h_comprometidos() const // O(1)
 
 void
 GaleShapley::
-casamentear() // O(N^2.log(N))
+casamentear() // O(N^4)
 {
-	primera_ronda(); // O(N^2.log(N))
+	primera_ronda(); // O(N^2)
+
+	// El bucle podría correrse (haciendo una estimación bruta y
+	// poco realista) N*N veces, así que sería en total O(N^4)
 	while (!todos_h_comprometidos()) // O(1)
-		nesima_ronda(); // O(N^2.log(N))
+		nesima_ronda(); // O(N^2)
 }