← Volver a los ejercicios

Lo que cobra cada operación

Cuatro cuentas sobre los algoritmos de la sesión.

1. lower_bound sobre 4096 elementos

Un vector ordenado de 4096 elementos. ¿Cuántas veces parte el rango por la mitad lower_bound hasta quedarse con una sola posición?

2. Borrar k elementos uno a uno

Un vector de n elementos y k de ellos, repartidos en el medio, se borran con it = v.erase(it). ¿Qué costo tiene en tiempo?

3. Un millón de consultas

Un vector de un millón de números y un millón de preguntas "¿está x?". ¿Cuál cuesta menos comparaciones?

4. El espacio de sort

Aparte del vector que ordena, ¿cuánto espacio pide sort?