Agrega graficos bien y corrige/agrega analisis de orden de GS y BT.

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

diff --git a/src/galeshapley.cpp b/src/galeshapley.cpp
index 494631cf632f49be945012ac9987e2921f9eab44..c71c65030f323a5b38b868d7be6ba79946531784 100644 (file)
--- a/src/galeshapley.cpp
+++ b/src/galeshapley.cpp
@@ -38,7 +38,7 @@ primera_ronda() // O(N^2.log(N))
 
 void
 GaleShapley::
 
 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)
 {
        // Todo el for es O(N^2)
        for (personas_type::iterator ih = hombres.begin(); // O(N)


@@ -91,7 +91,7 @@ nesima_ronda() // O(N^2.log(N))
                                for (Persona::ofertas_type::iterator i // O(N)
                                                = m.ofertas.begin();
                                                i != m.ofertas.end(); ++i)
                                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)
 
                                ph->rechazos[(&m)->nombre] = &m;
                                m.ofertas.clear(); // O(N)


@@ -118,10 +118,10 @@ todos_h_comprometidos() const // O(1)
 
 void
 GaleShapley::
 
 void
 GaleShapley::

-casamentear() // O(N^2.log(N))
+casamentear() // O(N^2)

 {
 {

-       primera_ronda(); // O(N^2.log(N))
+       primera_ronda(); // O(N^2)

        while (!todos_h_comprometidos()) // O(1)
        while (!todos_h_comprometidos()) // O(1)

-               nesima_ronda(); // O(N^2.log(N))
+               nesima_ronda(); // O(N^2)

 }
 
 }