From bf62b54574e0957ccde11a1bf49889986051cff0 Mon Sep 17 00:00:00 2001
From: Alberto Bertogli <albertogli@telpin.com.ar>
Date: Mon, 7 Nov 2005 01:52:03 +0000
Subject: [PATCH] Actualizar comentarios de los ordenes. Dado que ahora el
 orden del sort y la comparacion mejoraron, cambiaron varios ordenes en el GS.

---
 src/galeshapley.cpp | 20 ++++++++++----------
 src/persona.cpp     |  4 ++--
 2 files changed, 12 insertions(+), 12 deletions(-)

diff --git a/src/galeshapley.cpp b/src/galeshapley.cpp
index b2f2ac3..b50f5bc 100644
--- a/src/galeshapley.cpp
+++ b/src/galeshapley.cpp
@@ -14,7 +14,7 @@ GaleShapley(size_type capacidad):
 
 void
 GaleShapley::
-primera_ronda() // O(N^3.log(N^2))
+primera_ronda() // O(N^2.log(N))
 {
 	for (personas_type::iterator ih = hombres.begin(); // O(N)
 			ih != hombres.end(); ++ih)
@@ -27,7 +27,7 @@ primera_ronda() // O(N^3.log(N^2))
 		Persona& m = **im;
 		if (m.ofertas.empty()) // O(1)
 			continue;
-		m.ordenar_ofertas(); // O(N^2.log(N^2))
+		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)
@@ -36,9 +36,9 @@ primera_ronda() // O(N^3.log(N^2))
 
 void
 GaleShapley::
-nesima_ronda() // O(N^3.log(N^2))
+nesima_ronda() // O(N^2.log(N))
 {
-	// Todo el for es O(N^3)
+	// Todo el for es O(N^2)
 	for (personas_type::iterator ih = hombres.begin(); // O(N)
 			ih != hombres.end(); ++ih)
 	{
@@ -61,7 +61,7 @@ nesima_ronda() // O(N^3.log(N^2))
 		h.declarar_a(*pm); // O(1)
 	}
 
-	// Todo el for es O(N^3.log(N^2))
+	// Todo el for es O(N^2.log(N))
 	for (personas_type::iterator im = mujeres.begin(); // O(N)
 			im != mujeres.end(); ++im)
 	{
@@ -69,12 +69,12 @@ nesima_ronda() // O(N^3.log(N^2))
 		if (m.ofertas.empty()) // O(1)
 			continue;
 
-		m.ordenar_ofertas(); // O(N^2.log(N^2))
+		m.ordenar_ofertas(); // O(N.log(N))
 		Persona* ph = m.ofertas.front(); // O(1)
 		m.ofertas.pop_front(); // O(1)
 		if (m.estado == Persona::COMPROMETIDO)
 		{
-			if (m.cmp(*(m.pareja), *ph) < 0) // O(N)
+			if (m.cmp(*(m.pareja), *ph) < 0) // O(1)
 			{
 				// la oferta es mejor, rompemos el compromiso
 				m.comprometer_con(*ph); // O(N)
@@ -115,10 +115,10 @@ todos_h_comprometidos() const // O(N)
 
 void
 GaleShapley::
-casamentear() // O(N^4.log(N^2))
+casamentear() // O(N^3.log(N))
 {
-	primera_ronda(); // O(N^3.log(N^2))
+	primera_ronda(); // O(N^2.log(N))
 	while (!todos_h_comprometidos()) // O(N)
-		nesima_ronda(); // O(N^3.log(N^2))
+		nesima_ronda(); // O(N^2.log(N))
 }
 
diff --git a/src/persona.cpp b/src/persona.cpp
index 607e0e8..0016f3e 100644
--- a/src/persona.cpp
+++ b/src/persona.cpp
@@ -92,11 +92,11 @@ namespace
 /// Ordenamos las ofertas segun nuestras preferencias
 void
 Persona::
-ordenar_ofertas() // O(N^2.log(N^2))
+ordenar_ofertas() // O(N.log(N))
 {
 	// este sort es in-place y O(N.log(N))
 	// Más info en: http://www.sgi.com/tech/stl/sort.html
-	// Pero el PersonaCmp() es O(N)
+	// PersonaCmp() es O(1), asi que el orden es el mismo.
 	std::sort(ofertas.begin(), ofertas.end(), PersonaCmp(*this));
 }
 
-- 
2.43.0