Consulta MISION Complejidad Parte 1

[dgolzm]

Hola. Mí duda es que si en la función para el comando MISION se nos pide que sea O(log n) (refiriéndose a n como el número de agentes total), en caso de mandar nuevamente a alguien de esta misma agencia se considera en su complejidad en un caso general la búsqueda de un nuevo líder.

Mi consulta nace de que ahora mismo mi función es de complejidad O(log S) para la búsqueda de agencias, y la búsqueda de líder es O(1), por lo que mi función es de una complejidad menor a lo esperado (suponiendo O(log S) >= O(log n)). Pero como está descrito, se espera que la búsqueda de la agencia sea O(1) y que la búsqueda del agente con mayor nivel sea O(log n) (o sea, que se esperaría que siempre que sea necesario, se busque a un agente con complejidad O(log n)).

En resumen, mi función cuando el líder está disponible es de complejidad O(log S), pero cuando no lo está es O(n * log S), ya que se debe buscar al nuevo agente que debemos enviar.

¿Qué complejidad se toma al momento de revisarlo?

[JavierLarre]

Hola! Cuando nos referimos a n, nos referimos al numero total de agentes dentro de una agencia, pero no al total de agentes global, es decir que el evento MISSION debe tener una complejidad igual o menor a O(log n) o el logaritmo de agentes en la agencia.
Además, la búsqueda de un agente dentro de una agencia no debe depender de la cantidad de agencias, ya que S puede ser un número muy grande o muy pequeño, por lo tanto no estás cumpliendo con la complejidad exigida.
Te recomiendo replantear la manera en la que estás modelando el problema. Recuerda que el máximo de agencias en una ejecución es fija! Mucha suerte!