Home Algoritmos y Estructuras de Datos (VJ1215)

Curso 2021/2022

1. Análisis de algoritmos

Horas de clases presenciales: 8 (4 teoría + 4 prácticas)
Horas de trabajo no presencial: 8
Ratio: 2 horas no presenciales por cada clase de 2 horas

Recursos

Complementa las clases estudiando los siguientes apartados del capítulo 5 "Análisis de Algoritmos" del libro "Estructuras de datos en Java" (2000) de M. A. Weiss:

La edición en castellano "Estructuras de datos en Java" (2013) contiene erratas que nos hacen descartarla.

El concepto de coste amortizado lo introduciremos con un primer ejemplo en el tema siguiente.

Recursos opcionales

Si lo prefieres, puedes consultar la edición en inglés del mismo autor "Data structures and problem solving using Java" (2010). En su edición "Data Structures and Algorithm Analysis in C++" (2014) faltan algunos de los apartados recomendados.

Otra referencias opcionales que te pueden interesar si quieres profundizar en este tema o ver textos alternativos son:

Ejercicios

La sección "Ejercicios" contendrá en cada tema una propuesta de ejercicios a completar en el tiempo de trabajo de clase más el tiempo de trabajo no presencial de la asignatura.

No es obligatorio entregar las soluciones y no son puntuables, pero puedes pedir al profesor que revise lo que quieras y que te aclare cualquier duda, con el objetivo de aprender.

Cuando sea posible respetando las medidas sanitarias a las que nos obliga el COVID, puedes trabajar en pareja o en grupo si lo deseas, siempre que el objetivo sea que todos aprendáis a escribir las soluciones. Puedes pedir ayuda a otros estudiantes y comparar tu solución con las suyas.

Es importante no ver las soluciones antes de haber intentado resolver los ejercicios, porque debes aprender a escribirlas, no a leerlas.

Dedicaremos las primeras sesiones de laboratorio a adaptarnos a un nuevo lenguaje de programación (C++) y seguiremos introduciendo características de C++ poco a poco a lo largo del curso. Las soluciones en C++ que se proporcionan son también una ayuda para ir conociendo mejor el lenguaje.

En clase también veremos cómo trabajar usando Linux, empleando el compilador g++ y cualquier editor. Opcionalmente, quien lo prefiera podrá realizar todas las prácticas del curso con Online GDB.

En el ejercicio 3 veremos también cómo realizar comparaciones experimentales de diferentes soluciones algorítmicas a un mismo problema, midiendo tiempos de ejecución para diferentes tallas del problema y observando cómo crece el tiempo de ejecución cuando crece la talla.

Algunos de los siguientes ejercicios requieren que sepas que existen algoritmos que permiten ordenar un vector en tiempo O(n log n). A lo largo del curso estudiaremos algunos de esos algoritmos:

De momento no necesitas saber más de ellos.

Opcionalmente, en tu tiempo de trabajo no presencial puedes resolver también los ejercicios del siguiente apartado "Refuerzo de conceptos básicos: recursión". Te interesa mucho aprender a resolver esos ejercicios cuanto antes, si no sabes hacerlo ya.

  1. Clase de prácticas LA2 y LA4 07/09, LA1 y LA3 09/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 para descargarlos, compilarlos y ejecutarlos:

    mkdir AED
    cd AED

    wget http://www3.uji.es/~vjimenez/AULASVIRTUALES/AED-2122/C++/EjemplosInicialesC++/e01.cpp
    g++ e01.cpp && ./a.out

    wget http://www3.uji.es/~vjimenez/AULASVIRTUALES/AED-2122/C++/EjemplosInicialesC++/e02.cpp
    g++ e02.cpp && ./a.out

    wget http://www3.uji.es/~vjimenez/AULASVIRTUALES/AED-2122/C++/EjemplosInicialesC++/e03.cpp
    g++ e03.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++ e03.cpp -std=c++11 && ./a.out

    Opcionalmente, 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 y LA4 07/09, LA1 y LA3 09/09

    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. Utilízala para calcular desde f0 hasta f50 y observa el tiempo que tarda en calcular cada nuevo número (en el ejercicio 3 veremos cómo cronometrar ese tiempo con precisión). Compáralo con una función iterativa que obtenga cada número a partir de los dos anteriores. Observa la importante diferencia práctica entre ambas (de lo cual no puede deducirse que sea malo utilizar funciones recursivas).

    Solución

  3. Clase de prácticas LA2 y LA4 07/09, LA1 y LA3 09/09

    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. Implementa las dos versiones que se indican a continuación, para después compararlas experimentalmente:

    1. Empleando el algoritmo de búsqueda secuencial de forma no recursiva.

      Solución

      Busca errores

    2. Empleando el algoritmo de búsqueda binaria de forma no recursiva (suponiendo que es un vector ordenado).

      Solución

    Utilizando estos ejemplos se explicará en clase cómo medir tiempos de ejecución. Imita eso para comparar los tiempos de ejecución de las implementaciones de los algoritmos de búsqueda que has hecho.

    Después mira con detalle estas soluciones, que se analizarán también en clase y permitirán ver la importancia práctica de pasar los vectores por referencia.

    Para representar gráficamente los resultados puedes utilizar, por ejemplo, Gnuplot online: basta copiarlos en el panel "Data" y, si quieres, adaptar el contenido del panel "Plot script".

    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.

    1. Clase de teoría TE2 07/09, TE1 09/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 TE2 07/09, TE1 09/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 TE2 07/09, TE1 09/09

      ¿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?

    4. Clase de teoría TE2 07/09, TE1 09/09

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

    5. Clase de teoría TE2 07/09

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

    6. Clase de teoría TE1 16/09

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

  4. 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).

    i = 1 n i = 1 + 2 + + n i = 1 n i 2 = 1 2 + 2 2 + + n 2 i = 0 n 2 i = 2 0 + 2 1 + + 2 n

  5. Clase de teoría TE2 07/09

    Tenemos n 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(n2) 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

  6. 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

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

    Ayuda

    Solución

  8. Clase de prácticas LA2 y LA4 14/09, LA1 y LA3 16/09

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

    Solución

    Busca errores

  9. Clase de prácticas LA2 y LA4 14/09, LA1 y LA3 16/09

    Implementa una función que reciba un valor real x y un valor entero n y devuelva el resultado de calcular xn. 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.

  10. Clase de prácticas LA2 y LA4 14/09, LA1 y LA3 16/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

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

      Solución

      Busca errores

  11. Tras completar el ejercicio anterior, 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

  12. Tras completar el ejercicio anterior 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

  13. 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

  14. 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

  15. 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.

    Balanza

    Solución

Análisis de algoritmos recursivos (dedicaremos una clase a completar esto a final de curso)

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.

  1. Clase de teoría TE2 07/09 y 14/12, TE1 16/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

    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

  2. Clase de teoría TE1 02/12, TE2 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

  3. Clase de teoría TE1 02/12, TE2 14/12

    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

    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

  4. Clase de teoría TE1 02/12, TE2 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 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

  5. Clase de teoría TE1 02/12, TE2 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

    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

  6. Clase de teoría TE1 02/12, TE2 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];
         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

  7. Clase de teoría TE1 02/12, TE2 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

Opcionalmente, en los exámenes de cursos pasados puedes encontrar más ejercicios de análisis de costes, si quieres seguir practicando.

Refuerzo de conceptos básicos: recursión

En esta asignatura aparecerán con frecuencia algoritmos recursivos, en unas ocasiones deberás leerlos y entenderlos y en otras deberás escribirlos.

Si tienes dificultades para entender la recursión, estudia primero los apartados 10.1, 10.2 (exceptuando el ejemplo de análisis sintáctico) y 10.3 del capítulo 10 "Implementación de TADs: recursión, análisis de algoritmos y algoritmos estándar" del libro "TADs, estructuras de datos y resolución de problemas con C++" (2006) de L. R. Nyhoff.

El vídeo "What on Earth is Recursion?" de Computerphile te puede interesar también (observa que puedes ponerle subtítulos traducidos automáticamente al castellano si te hace falta).

Como refuerzo, resuelve de forma recursiva cada uno de los siguientes problemas (debes aprender a escribir las soluciones, y eso es muy diferente de leer las soluciones).

  1. Contar las cifras de un entero no negativo n.
    Solución

  2. Contar las veces que una cifra c aparece en un entero no negativo n.
    Solución

  3. Averiguar si todas las cifras de un entero no negativo n son pares.
    Solución

  4. Averiguar si un dato d aparece en un vector v.
    Solución (versión 1) Solución (versión 2)

  5. Contar las veces que un dato d aparece en un vector v.
    Solución

  6. Mostrar en la salida estándar los elementos de un vector v en orden natural, del primero al último, uno en cada línea.
    Solución

  7. Mostrar en la salida estándar los elementos de un vector v en orden inverso, del último al primero, uno en cada línea.
    Solución

  8. Averiguar si un vector no vacío v está ordenado de menor a mayor.
    Solución (versión 1) Solución (versión 2)

  9. Encontrar el menor elemento en un vector no vacío v.
    Solución

  10. Averiguar si todos los elementos de un vector no vacío v son mayores que un dato d.
    Solución (versión 1) Solución (versión 2)

El tiempo invertido debería ser parte de las 300 horas de programación de primer curso.