Termina informe.

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

diff --git a/src/galeshapley.cpp b/src/galeshapley.cpp
index c71c65030f323a5b38b868d7be6ba79946531784..5667dfec6e3b517f7c6229d684bf2db21f904658 100644 (file)
--- 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,16 +22,16 @@ 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++;
        }
 }
@@ -63,7 +63,7 @@ nesima_ronda() // O(N^2)
                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)
                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)
@@ -118,9 +116,12 @@ todos_h_comprometidos() const // O(1)
 
 void
 GaleShapley::
-casamentear() // O(N^2)
+casamentear() // O(N^4)
 {
        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)
 }