Algoritmos y Estructuras de Datos (VJ1215)

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;
}
      

Problema que resuelve: mezcla de vectores ordenados (dados dos vectores ordenados de menor a mayor, junta todos sus elementos en un nuevo vector que tambien estará ordenado de menor a mayor).

Coste temporal en el peor caso: O(n) siendo n la suma de las tallas de los dos vectores dados. Se deduce observando que depende de cuántas veces se incrementa k.

En este ejercicio debes entender que las instrucciones internas a los dos bucles anidados no se ejecutan en el peor caso m·n veces, siendo m la talla del primer vector y n la talla del segundo vector. El bucle externo hace m iteraciones, pero el bucle interno no hace n iteraciones por cada iteración del bucle externo, no empieza cada vez a recorrer el segundo vector desde la posición 0 sino desde donde había llegado.