Simulación

Encuentra el bucle escondido

Texto

función usuarios_activos(eventos, usuarios):    activos ← array vacío    para cada e en eventos:                    # 1 000 000 eventos        si e.tipo = "login" y no contiene(activos, e.usuario):            agregar(activos, e.usuario)    devolver activos

Hay 100 000 usuarios distintos.

En usuarios_activos, que recorre 1 000 000 de eventos y llama a contiene sobre el array activos antes de agregar, hay 100 000 usuarios distintos. ¿Qué patrón es y cuántas comparaciones hace, en orden de magnitud?contiene en un bucle: hasta 10⁶ × 10⁶ = 10¹² comparaciones, si el array llegara a un millónOrdenar en cada iteración: un millón de ordenamientos de 10⁵ elementos, unas 10¹² comparacionescontiene en un bucle: hasta 10⁶ × 10⁵ = 10¹¹ comparaciones; con un conjunto hash, unas 10⁶Es O(n), un solo bucle: unas 10⁶ comparaciones en total y no hay nada que cambiar