Agrega gráficos de orden y otras correcciones mínimas al informe.

[z.facultad/75.29/susanita.git] / src / galeshapley.cpp

diff --git a/src/galeshapley.cpp b/src/galeshapley.cpp
index b2f2ac3363365304b559518ddc4355772c994f8d..c71c65030f323a5b38b868d7be6ba79946531784 100644 (file)
--- a/src/galeshapley.cpp
+++ b/src/galeshapley.cpp
@@ -14,8 +14,9 @@ GaleShapley(size_type capacidad):
 
 void
 GaleShapley::
-primera_ronda() // O(N^3.log(N^2))
+primera_ronda() // O(N^2.log(N))
 {
+       cant_comprometidos = 0;
        for (personas_type::iterator ih = hombres.begin(); // O(N)
                        ih != hombres.end(); ++ih)
        {
@@ -27,18 +28,19 @@ 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)
+               cant_comprometidos++;
        }
 }
 
 void
 GaleShapley::
-nesima_ronda() // O(N^3.log(N^2))
+nesima_ronda() // O(N^2)
 {
-       // 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 +63,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,14 +71,16 @@ 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
+                               // No cambiamos la cantidad de comprometidos
+                               // porque estamos cambiando uno por otro
                                m.comprometer_con(*ph); // O(N)
                        }
                        else
@@ -87,7 +91,7 @@ nesima_ronda() // O(N^3.log(N^2))
                                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)
@@ -96,29 +100,28 @@ nesima_ronda() // O(N^3.log(N^2))
                else
                {
                        m.comprometer_con(*ph); // O(N)
+                       cant_comprometidos++;
                }
        }
 }
 
 bool
 GaleShapley::
-todos_h_comprometidos() const // O(N)
+todos_h_comprometidos() const // O(1)
 {
-       // FIXME: podemos ver de poner esto adentro de nesima_ronda()
-       for (personas_type::const_iterator ih = hombres.begin(); // O(N)
-                       ih != hombres.end(); ++ih)
-               if ((*ih)->estado != Persona::COMPROMETIDO)
-                       return false;
-       return true;
+       if (cant_comprometidos == capacidad) {
+               return true;
+       }
+       return false;
 }
 
 
 void
 GaleShapley::
-casamentear() // O(N^4.log(N^2))
+casamentear() // O(N^2)
 {
-       primera_ronda(); // O(N^3.log(N^2))
-       while (!todos_h_comprometidos()) // O(N)
-               nesima_ronda(); // O(N^3.log(N^2))
+       primera_ronda(); // O(N^2)
+       while (!todos_h_comprometidos()) // O(1)
+               nesima_ronda(); // O(N^2)
 }