Actualizar comentarios de los ordenes.

Dado que ahora el orden del sort y la comparacion mejoraron, cambiaron varios
ordenes en el GS.

diff --git a/src/galeshapley.cpp b/src/galeshapley.cpp
index b2f2ac3363365304b559518ddc4355772c994f8d..b50f5bc861591f25a8c2e00c21ebdbc24a9d3cf9 100644 (file)
--- a/src/galeshapley.cpp
+++ b/src/galeshapley.cpp
@@ -14,7 +14,7 @@ GaleShapley(size_type capacidad):
 
 void
 GaleShapley::
 
 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)
 {
        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;
                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)
                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::
 
 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)
        {
        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)
        }
 
                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)
        {
        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;
 
                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)
                {
                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)
                        {
                                // 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::
 
 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)
        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 607e0e8a0d36f0fff0464c9cdcb3490d61984e4c..0016f3e01eb7aa559744ae90c40e78370ebf916b 100644 (file)
--- a/src/persona.cpp
+++ b/src/persona.cpp
@@ -92,11 +92,11 @@ namespace
 /// Ordenamos las ofertas segun nuestras preferencias
 void
 Persona::
 /// 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
 {
        // 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));
 }
 
        std::sort(ofertas.begin(), ofertas.end(), PersonaCmp(*this));
 }