Algoritmos y Estructuras de Datos (VJ1215)

1. Clase de prácticas LA2 12/09, LA1 y LA3 14/09

   Asegúrate de que entiendes estos tres ejemplos iniciales de C++, explicados en la primera sesión de prácticas.

   Prueba esto en un terminal tras guardarlos, para compilarlos y ejecutarlos:

   g++ ejemplo_for.cpp && ./a.out

g++ ejemplo_vector.cpp && ./a.out

g++ ejemplo_funcion.cpp && ./a.out

   En el tercer ejemplo se hace uso de C++11 para inicializar el vector. Si en tu ordenador tienes una versión de g++ más antigua que la que tenemos este curso en las aulas, es posible que tengas que informarle de que usas C++11:

   
g++ ejemplo_funcion.cpp -std=c++11 && ./a.out


   Pueba a compilar los mismos ejemplos con Online GDB. En el resto del curso puedes seguir trabajando con él si lo prefieres.

2. Clase de prácticas LA2 12/09, LA1 y LA3 14/09

   1. Implementa una función recursiva que calcule y devuelva el n-ésimo número de Fibonacci, pasándole n. Haz una primera versión aplicando directamente esta definición recursiva.

      Solución

   2. Resuelve el mismo problema con una función iterativa que obtenga cada número a partir de los dos anteriores.

      Utilíza ambas soluciones para calcular desde f₀ hasta f₅₀. Observa el tiempo que tardan en calcular cada nuevo número (en el apartado c verás cómo cronometrar ese tiempo con precisión) y la importante diferencia práctica entre ambas (de lo cual no puede deducirse que sea malo utilizar funciones recursivas: lo que hace tan lenta esa solución no es su naturaleza recursiva sino el hecho de estar repitiendo cálculos).

      Solución

   3. Consulta aquí el resultado de comparar experimentalmente las dos soluciones anteriores midiendo sus tiempos de ejecución.

      Nota sobre evaluación: Medir experimentalmente tiempos de ejecución no será materia de examen, aunque éste es un ejercicio importante para convencerte de la importancia práctica del contenido de la asignatura. Si no estás convencido de eso, lo puedes pasar mal estudiándola. Por otra parte, la comparación experimental de algoritmos te resultará útil cuando el análisis teórico no baste para elegir uno.

3. Clase de prácticas LA2 12-19/09, LA1 y LA3 14-21/09

   1. ¿Conoces algún algoritmo, entre los que has estudiado en primer curso, que tenga coste temporal O(log n) en el peor caso? ¿Cuál es su coste temporal en el mejor caso?

   2. Implementa en C++ una función que reciba como argumentos un vector de enteros y un dato que queremos buscar en dicho vector. La función debe "devolver" (no lo confundas con "mostrar") la posición del dato si lo encuentra y -1 en caso contrario. Si el dato aparece más de una vez, debe devolver una (cualquiera) de las posiciones en que aparece.

      Hazlo empleando el algoritmo de búsqueda secuencial de forma no recursiva.

      Solución

      Aprende más ayudando a otros estudiantes

   3. Resuelve de nuevo el problema anterior empleando esta vez el algoritmo de búsqueda binaria de forma no recursiva (suponiendo que es un vector ordenado).

      Solución

   4. Clase de teoría TE1 14/09

      Después mira con detalle esta comparación experimental midiendo tiempos, que se analizará en clase de teoría. También la utilizaremos, en la siguiente clase de prácticas, para ver la importancia práctica de pasar los vectores por referencia.

4. Sustituye la implementación no recursiva del algoritmo de búsqueda binaria del ejercicio 3.c por una implementación recursiva.

   Solución

   Aprende más ayudando a otros estudiantes

5. 1. Clase de teoría TE1 14/09

      Analiza el coste temporal, en el mejor y en el peor caso, de este algoritmo para buscar la posición de un dato en un vector de talla n (es la solución del ejercicio 3.a). Indica cuándo se dan el mejor y el peor caso.

      int busquedaSecuencial(const vector<int> & v, int dato) {
         for (int i = 0; i < v.size(); i++)
            if (v[i] == dato)
               return i;
         return -1;
      }
      		

      Solución

   2. Clase de teoría TE1 14/09

      Analiza el coste temporal, en el mejor y en el peor caso, de este algoritmo para sumar los datos de un vector de talla n. ¿Coinciden los resultados con los del apartado anterior? ¿Por qué?

      int sumar(const vector<int> & v) {
         int suma = 0;
         for (int i = 0; i < v.size(); i++)
            suma += v[i];
         return suma;
      }
      		

      ¿Cambiaría alguno de esos costes si implementásemos así el algoritmo?

      int sumar(const vector<int> & v) {
         if (v.size() == 0)
            return 0;
         if (v.size() == 1)
            return v[0};
         int suma = v[0];
         for (int i = 1; i < v.size(); i++)
            suma += v[i];
         return suma;
      }
      		

      Solución

   3. Clase de teoría TE1 21/09

      Analiza el coste temporal, en el mejor y en el peor caso, del algoritmo de ordenación por inserción.

   4. Analiza el coste temporal, en el mejor y en el peor caso, del algoritmo de ordenación por selección.

   5. Resuelve este ejercicio sobre costes temporales de bucles (incluye las soluciones).

6. Clase de teoría TE1 21/09

   Averigua, consultando por ejemplo la página Sumatorio de la Wikipedia, cómo calcular estos sumatorios, que no debes confundir entre sí (en estos sumatorios se usa MathML, para verlos correctamente es recomendable utilizar alguna versión reciente de Firefox).

   $$\sum _{i=1}^{n}i=1+2+\dots +n$$ $$\sum _{i=0}^n{2}^i=2^0+2^1+\dots +2^n$$

7. Tenemos n ≥ 2 datos de tipo real almacenados en un vector y queremos encontrar, entre todos los posibles pares de datos, un par tal que la diferencia entre los dos valores del par sea mínima (por ejemplo, para emparejar a los dos jugadores que tienen la puntuación más similar en un videojuego). ¿Cómo resolverías el problema, y qué coste tendría, sin ordenar el vector? ¿Sería mejor ordenar primero el vector con un algoritmo de coste O(n²) y aprovechar después esa ordenación? ¿Sería mejor ordenarlo con un algoritmo de coste O(n log n) y aprovechar después esa ordenación? ¿Qué harías si no fuese posible modificar el vector y cómo afectaría eso al coste temporal?

   Solución

8. Propón un algoritmo para averiguar en tiempo O(n log n) si dos vectores contienen los mismos datos y en las mismas cantidades, sabiendo que ambos son de talla n y no están necesariamente ordenados,

   Ayuda

   Solución

9. Propón un algoritmo para averiguar en tiempo O(n log n) si un vector de talla n contiene elementos duplicados.

   Ayuda

   Solución

10. Clase de prácticas LA2 19/09, LA1 y LA3 21/09

    Implementa una función recursiva que reciba un valor real x y un valor entero n y devuelva el resultado de calcular xⁿ. Contempla la posibilidad de que el exponente sea negativo. Tu solución debe ejecutarse en tiempo O(log |n|).

    Ayuda

    Solución

    También es válida esta solución de M. A. Weiss (aunque en ella no trabaja con valores de tipo real). Puedes encontrar una explicación en el apartado 2.4.4 "Logarithms in the Running Time" (páginas 87-88) de su libro "Data Structures and Algorithm Analysis in C++" (2014). Puedes encontrar una explicación alternativa en el apartado 1.6 "Un ejemplo elaborado: exponenciación" del libro "Estructuras de datos, algoritmos y programación orientada a objetos" (1998) de G. L. Heileman y en la página "Exponenciación binaria" de la Wikipedia.

11. Clase de prácticas LA2 19/09, LA1 y LA3 21/09

    En un vector v1 tenemos números ordenados de menor a mayor sin repetidos. En otro vector v2 tenemos números con esas mismas condiciones. Queremos contar cuántos números comunes tienen v1 y v2.

    1. Diseña un algoritmo eficiente para resolver ese problema e impleméntalo en C++, suponiendo que no puedes utilizar llamadas recursivas.

       Ayuda (mírala después de pensar la solución)

       Solución

       Aprende más ayudando a otros estudiantes

    2. Resuelve de nuevo el mismo problema recursivamente, sin utilizar ningún bucle.

       Solución

       Aprende más ayudando a otros estudiantes

12. Tras completar el ejercicio 11, diseña un algoritmo eficiente para resolver el problema de mezclar dos vectores ordenados. Su entrada serán dos vectores de números reales, cada uno de los cuales estará ordenado de menor a mayor y podrá contener elementos repetidos. Su salida debe ser un nuevo vector que contenga todos los elementos de ambos vectores ordenados también de menor a mayor.

    Por ejemplo, si los vectores de entrada son [11, 22, 33.3, 33.3, 35] y [10, 33.3, 40] el resultado debe ser [10, 11, 22, 33.3, 33.3, 33.3, 35, 40].

    La solución de este problema será una subrutina del algoritmo de ordenación por mezcla mergesort, como veremos en el tema 5.2.

    1. Resuelve el problema sin utilizar recursión.

       Analiza el tiempo de ejecución de tu solución en el peor caso y exprésalo en notación O.

       Solución

    2. Resuelve el mismo problema sin utilizar ningún bucle, con el mismo coste temporal.

       Solución

13. Tras completar el ejercicio 12 y entender las soluciones propuestas, indica qué problema resuelve el algoritmo siguiente y analiza su coste temporal en el peor caso.

    vector<float> misterio(const vector<float> & a, const vector<float> & b) {
       vector<float> c(a.size() + b.size());
       int i = 0, j = 0, k = 0;
       while ( i < a.size() ) {
          while ( j < b.size() && b[j] <= a[i] ) {
             c[k] = b[j];
             k++;
             j++;
          }
          c[k] = a[i];
          k++;
          i++;
       }
       while ( j < b.size() ) {
          c[k] = b[j];
          k++;
          j++;
       }
       return c;
    }
    	    

    Solución

14. Supongamos que en un vector de cadenas A tienes los DNI de los clientes de tu empresa de videojuegos y en otro vector B tienes los DNI de los clientes que ya han comprado el último videojuego lanzado al mercado. En una campaña de marketing quieres obtener a partir de ellos un vector con los DNI de los clientes que no han comprado ese videojuego. Propón un algoritmo para resolver el problema y analiza su coste computacional en cada uno de los casos siguientes:

    1. si ninguno de los dos vectores está ordenado;

    2. si el vector A ya está ordenado y el B no;

    3. si el vector B ya está ordenado y el A no; y

    4. si ambos están ordenados.

    ¿Vale la pena invertir tiempo en ordenar los vectores inicialmente para resolver el problema cuando no están ordenados?

    Solución

15. Tienes que encontrar un número secreto n que es entero positivo y no sabes en qué rango se encuentra. Cada vez que hagas un intento fallido te dirán si el número secreto es mayor o menor que el que has propuesto. Propón un algoritmo para encontrar el número secreto realizando O(log n) intentos.

    Solución

16. Tienes n monedas, siendo n potencia de 2, y sabes que una de ellas es falsa y pesa menos que las demás. Para encontrarla dispones de una balanza de dos platillos, en los que puedes poner tantas monedas como quieras. Diseña un procedimiento que te permita encontrar la moneda falsa realizando O(log n) pesadas (la única operación cuyo coste nos interesa, por tanto, es la de usar la balanza para pesar; es lo que pasaría, por ejemplo, si hubiera que pagar una cantidad fija por cada pesada). Después modifícalo, si hace falta, para evitar la necesidad de que n sea potencia de 2.

    

    Solución

Cuando un algoritmo realiza un bucle, su coste depende de cuántas iteraciones hace el bucle y cuánto cuesta cada iteración. Análogamente, cuando un algoritmo realiza llamadas recursivas, su coste dependerá de cuántas llamadas recursivas se hacen y cuánto cuesta cada llamada. En los siguientes ejercicios vas a analizar eso. Realízalos en el orden propuesto, la dificultad es creciente y cada ejercicio se apoya en lo aprendido en los anteriores.

17. Clase de teoría TE1 21/09

    1. Analiza el coste temporal y espacial, en el mejor y en el peor caso, del siguiente algoritmo iterativo para calcular el factorial de un número entero no negativo.

       int factorial(int n) {
          int resultado = 1;
          for (int i = 2; i <= n; i++)
             resultado = resultado * i;
          return resultado;
       }
       		

       ¿Cambiaría alguno de esos costes con la siguiente modificación?

       int factorial(int n) {
          if (n <= 1)
             return 1;	 
          else {	 
             int resultado = 1;
             for (int i = 2; i <= n; i++)
                resultado = resultado * i;
             return resultado;
          }
       }
       		

       Solución

    2. Analiza el coste temporal y espacial, en el mejor y en el peor caso, del siguiente algoritmo recursivo para realizar el mismo cálculo:

       int factorial(int n) {
          if (n <= 1)
             return 1;
          else
             return n * factorial(n - 1);
       }
       		

       Solución

18. 1. Analiza el coste temporal y espacial, en el mejor y en el peor caso, del siguiente algoritmo recursivo para averiguar si todas las cifras de un entero son pares.

       bool verificarCifrasPares(int n) {
          if (n == 0)
             return true;
          return n % 2 == 0 && verificarCifrasPares(n / 10);
       }
       		

       Ayuda: mira la página "¿Cuántas cifras tiene un número?" de Félix Rodríguez Díaz.

       Solución

    2. ¿Cómo cambiarían esos costes al poner los operandos del operador && en el orden contrario?

       bool verificarCifrasPares(int n) {
          if (n == 0)
             return true;
          return verificarCifrasPares(n / 10) && n % 2 == 0;
       }
       		

       Solución

19. Clase de teoría TE1 14/12

    

    Analiza el coste temporal y espacial, en el mejor y en el peor caso, del siguiente algoritmo recursivo para resolver el problema de las Torres de Hanoi.

    void dimeComoMover(int cantidadDiscos, int origen, int destino) {
       if (cantidadDiscos == 1)
          cout << "Mueve un disco de la aguja " <<  origen
               << " a la aguja " << destino << endl;
       else {
          int auxiliar = 6 - origen - destino;
          dimeComoMover(cantidadDiscos - 1, origen, auxiliar);
          cout << "Mueve un disco de la aguja " <<  origen
               << " a la aguja " << destino << endl;
          dimeComoMover(cantidadDiscos - 1, auxiliar, destino);
       }
    }
    void resolverLasTorresDeHanoi(int cantidadDiscos) {
       dimeComoMover(cantidadDiscos, 1, 3);
    }
                

    Código de prueba en onlineGDB

    Solución

20. Analiza el coste temporal y espacial, en el mejor y en el peor caso, de la siguiente solución alternativa del ejercicio 10. ¿Se pueden reducir esos costes?

    float potencia(float base, int exponente) {
       if (exponente < 0)
          return 1 / potencia(base, -exponente);
       if (exponente == 0)
          return 1;
       if (exponente % 2 == 1)
          return base
                 * potencia(base, exponente / 2)
                 * potencia(base, exponente / 2);
       return potencia(base, exponente / 2)
              * potencia(base, exponente / 2);
    }
    	    

    Solución

21. 1. Analiza el coste temporal y espacial, en el mejor y en el peor caso, del siguiente algoritmo recursivo para averiguar si un dato aparece en un vector de talla n

       bool buscar(const vector<float> & v, float dato, int fin) {
          if (fin < 0)
             return false;
          if (v[fin] == dato)
             return true;
          return buscar(v, dato, fin - 1);
       }
       
       bool buscar(const vector<float> & v, float dato) {
          return buscar(v, dato, v.size() - 1);
       }
       		

       Solución

    2. ¿Cuál es el coste espacial, en el mejor y en el peor caso, sin contar el coste del vector?

       Solución

    3. ¿Cuáles serían los 4 costes analizados en el apartado a si, sin cambiar nada más, el vector se pasase por valor en vez de por referencia?

       bool buscar(vector<float> v, float dato, int fin) {
          if (fin < 0)
             return false;
          if (v[fin] == dato)
             return true;
          return buscar(v, dato, fin - 1);
       }
       
       bool buscar(vector<float> v, float dato) {
          return buscar(v, dato, v.size() - 1);
       }
       		

       Ayuda

       Solución

22. 1. Analiza el coste temporal y espacial, en el mejor y en el peor caso, del siguiente algoritmo recursivo para averiguar si un dato aparece en un vector ordenado de talla n.

       bool buscar(const vector<float> & v, float dato, int inicio, int fin) {
          if (inicio <= fin) {
             int medio = (inicio + fin) / 2;
             if (v[medio] < dato)
       	 return buscar(v, dato, medio + 1, fin);
             else if (v[medio] > dato)
       	 return buscar(v, dato, inicio, medio - 1);
             else
       	 return true;
          }
          return false;
       }
       
       bool buscar(const vector<float> & v, float dato) {
          return buscar(v, dato, 0, v.size() - 1);
       }
       		

       Solución

    2. ¿Cuál es el coste espacial, en el mejor y en el peor caso, sin contar el coste del vector?

       Solución

    3. ¿Cuáles serían los 4 costes analizados en el apartado a si, sin cambiar nada más, el vector se pasase por valor en vez de por referencia?

       bool buscar(vector<float> v, float dato, int inicio, int fin) {
          if (inicio <= fin) {
             int medio = (inicio + fin) / 2;
             if (v[medio] < dato)
       	 return buscar(v, dato, medio + 1, fin);
             else if (v[medio] > dato)
       	 return buscar(v, dato, inicio, medio - 1);
             else
       	 return true;
          }
          return false;
       }
       
       bool buscar(vector<float> v, float dato) {
          return buscar(v, dato, 0, v.size() - 1);
       }
       		

       Solución

23. Clase de teoría TE1 14/12

    1. Analiza el coste temporal y espacial, en el mejor y en el peor caso, del siguiente algoritmo recursivo para averiguar si un dato aparece en un vector de talla n.

       bool buscar(const vector<float> & v, float dato, int inicio, int fin) {
          if (inicio > fin)
             return false;
          int medio = (inicio + fin) / 2;
          if (v[medio] == dato)
             return true;
          if (buscar(v, dato, inicio, medio - 1))
             return true;
          if (buscar(v, dato, medio + 1, fin))
             return true;
          return false;  
       }
       bool buscar(const vector<float> & v, float dato) {
          return buscar(v, dato, 0, v.size() - 1);
       }
       		

       Solución

    2. ¿Cuál es el coste espacial, en el mejor y en el peor caso, sin contar el coste del vector?

       Solución

    3. ¿Cuáles serían los 4 costes analizados en el apartado a si, sin cambiar nada más, el vector se pasase por valor en vez de por referencia?

       bool buscar(vector<float> v, float dato, int inicio, int fin) {
          if (inicio > fin)
             return false;
          int medio = (inicio + fin) / 2;
          if (v[medio] == dato)
             return true;
          if (buscar(v, dato, inicio, medio - 1))
             return true;
          if (buscar(v, dato, medio + 1, fin))
             return true;
          return false;  
       }
       bool buscar(vector<float> v, float dato) {
          return buscar(v, dato, 0, v.size() - 1);
       }
       		

       Solución

24. 1. Analiza el coste temporal y espacial, en el mejor y en el peor caso, del siguiente algoritmo recursivo para averiguar si un dato aparece en un vector ordenado de talla n.

       bool buscar(const vector<float> & v, float dato, int fin) {
          int medio = fin / 2;
          if (v[medio] > dato) {
             if (medio == 0)
                return false;
             return buscar(v, dato, medio - 1);
          }
          for (int i = medio; i <= fin; i++)
             if (v[i] == dato)
                return true;
          return false;
       }
       bool buscar(const vector<float> & v, float dato) {
          return buscar(v, dato, v.size() - 1);
       }
       		

       Solución

    2. ¿Cuál es el coste espacial, en el mejor y en el peor caso, sin contar el coste del vector?

       Solución

    3. ¿Cuáles serían los 4 costes analizados en el apartado a si, sin cambiar nada más, el vector se pasase por valor en vez de por referencia?

       bool buscar(vector<float> v, float dato, int fin) {
          int medio = fin / 2;
          if (v[medio] > dato) {
             if (medio == 0)
                return false;
             return buscar(v, dato, medio - 1);
          }
          for (int i = medio; i <= fin; i++)
             if (v[i] == dato)
                return true;
          return false;
       }
       bool buscar(vector<float> v, float dato) {
          return buscar(v, dato, v.size() - 1);
       }
       		

       Solución

25. 1. Analiza el coste temporal y espacial, en el mejor y en el peor caso, del siguiente algoritmo recursivo para buscar el máximo en un vector de talla n ≥ 1. Justifica brevemente tus respuestas.

       int maximo(const vector<int> & v) { // Suponiendo v.size() >= 1
          if (v.size() == 1) return v[0];
          vector<int> resto(v.size() - 1);
          for (int i = 1; i < v.size(); i++)
             resto[i - 1] = v[i];
          int maximoResto = maximo(resto);
          if (maximoResto > v[0])
             return maximoResto;
          else
             return v[0];
       }
       		

       Solución

    2. ¿Cuál es el coste espacial, en el mejor y en el peor caso, sin contar el coste de los vectores?

       Solución

    3. ¿Cuáles serían los 4 costes analizados en el apartado a si, sin cambiar nada más, el vector se pasase por valor en vez de por referencia?

       int maximo(vector<int> v) { // Suponiendo v.size() >= 1
          if (v.size() == 1) return v[0];
          vector<int> resto(v.size() - 1);
          for (int i = 1; i < v.size(); i++)
             resto[i - 1] = v[i];
          int maximoResto = maximo(resto);
          if (maximoResto > v[0])
             return maximoResto;
          else
             return v[0];
       }
       		

       Solución

26. Clase de teoría TE1 14/12

    1. Analiza el coste temporal y espacial, en el mejor y en el peor caso, del siguiente algoritmo recursivo para buscar el máximo en un vector de talla n ≥ 1. Justifica brevemente tus respuestas.

       int maximo(const vector<int> & v) { // Suponiendo v.size() >= 1
          if (v.size() == 1) return v[0];
          int mitad = v.size() / 2;
          vector<int> izquierda(mitad);
          for (int i = 0; i < mitad; i++)
             izquierda[i] = v[i];
          vector<int> derecha(v.size() - mitad);
          for (int i = mitad, j = 0; i < v.size(); i++, j++)
             derecha[j] = v[i];
          int maximoIzquierda = maximo(izquierda);
          int maximoDerecha = maximo(derecha);
          if (maximoIzquierda >= maximoDerecha)
             return maximoIzquierda;
          else
             return maximoDerecha;
       }
       		

       Solución

    2. ¿Cuál es el coste espacial, en el mejor y en el peor caso, sin contar el coste de los vectores?

       Solución

    3. ¿Cuáles serían los 4 costes analizados en el apartado a si, sin cambiar nada más, el vector se pasase por valor en vez de por referencia?

       int maximo(vector<int> v) { // Suponiendo v.size() >= 1
          if (v.size() == 1) return v[0];
          int mitad = v.size() / 2;
          vector<int> izquierda(mitad);
          for (int i = 0; i < mitad; i++)
             izquierda[i] = v[i];
          vector<int> derecha(v.size() - mitad);
          for (int i = mitad, j = 0; i < v.size(); i++, j++)
             derecha[j] = v[i];
          int maximoIzquierda = maximo(izquierda);
          int maximoDerecha = maximo(derecha);
          if (maximoIzquierda >= maximoDerecha)
             return maximoIzquierda;
          else
             return maximoDerecha;
       }
       		

       Solución

27. Clase de teoría TE1 14/12

    Considera la implementación del Tipo Abstracto de Datos Pila que puedes encontrar en esta carpeta (o en este enlace de OnlineGDB). En ella se utiliza internamente un vector para guardar los datos de la pila. En el método apilar, se duplica el tamaño de ese vector si está lleno. Para ello, se utiliza el método resize de la clase vector, cuyo coste temporal es O(n), siendo n el nuevo tamaño del vector.

    1. ¿Cuál es el coste temporal en el peor caso de ese método apilar?

    2. ¿Cuál es el coste temporal en el peor caso de realizar una secuencia de n operaciones apilar como las que se realizan en el siguiente fragmento de código?

       Pila p;		    
       for (int i = 1; i <= n; i++)
          p.apilar(10 * i);
       		  

    3. ¿Cuál es el coste amortizado del método apilar?

    Solución

28. Un árbol biselado (splay tree) es un árbol binario de búsqueda en el que los algoritmos de inserción y eliminación son diferentes de los que hemos estudiado en el tema 3, consiguiendo tener coste amortizado O(log n) y coste en el peor caso O(n). Sin necesidad de saber cómo funcionan esos algoritmos, sabiendo que tienen esos costes, analiza cuál sería el coste temporal en el peor caso del algoritmo de ordenación del ejercicio 13 del tema 3 si sustituimos el árbol por un árbol biselado.

    void ordenar(vector<int> & v) {
    
       Multiconjunto multiconjunto;
    
       for (int dato : v)
          multiconjunto.insertar(dato);
    
       v = multiconjunto.obtenerOrdenados();
    
    }
    	      

    Solución

29. Clase de teoría TE1 14/12

    Un montículo de Fibonacci es una estructura de datos que permite implementar colas de prioridad con estos costes temporales:

    	Coste en el peor caso	Coste amortizado
    Insertar	O(1)	O(1)
    ConsultarMínimo	O(1)	O(1)
    EliminarMínimo	O(n)	O(log n)
    DisminuirPrioridad	O(n)	O(1)

    Sin necesidad de conocer cómo funcionan los montículos de Fibonacci, teniendo en cuenta solamente esos costes, ¿cuál sería el coste temporal en el peor caso del algoritmo de Dijkstra si la cola de prioridad se implementase utilizando un montículo de Fibonacci? Recuerda el ejercicio 14 del tema 6.

    Solución

30. Teniendo en cuenta la tabla de costes del ejercicio anterior, analiza el coste temporal en el peor caso del algoritmo de Huffman cuando se aplica a un alfabeto que tiene n caracteres, suponiendo que la cola de prioridad que utiliza el algoritmo se implementa empleando un montículo de Fibonacci. Recuerda el ejercicio 3 del tema 5.1.

    Solución