Curso 2024/2025
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.