Sería bueno saber de qué tipo de datos estamos hablando. ¿Cuántos usuarios existen? ¿Cuántos estarán en línea en promedio? ¿Cómo es la proporción de "usuarios vistos" en comparación con todos los usuarios (escasos frente a densos)?
Modificación de su algoritmo No haga estallar el primero, elija un elemento aleatorio del conjunto de usuarios en línea. ¡Esto debería mejorar el equilibrio y puede ayudar con la complejidad amortizada dependiendo de la proporción de estos dos conjuntos!
Algoritmo alternativo (más estructurado; sigue siendo malo en el peor de los casos; debería ser bueno si escaso visto )
- Manténgase visto como un árbol balanceado (inserción O(log n))
- Manténgase en línea como un árbol equilibrado.
- Si bien no se eligieron suficientes usuarios:
- Buscar el primer espacio en visto (por ejemplo, [0,1,3,7] -> 2; O(log n) de acuerdo con SO-link)
- Buscar primer usuario>=valor de brecha (O(log n))
- Si el usuario
- -> escoger
- Más
- -> agregar valor de brecha elegido temporalmente (por este momento; modelo-decisión con qué frecuencia actualizar en línea ) a visto O limitar la búsqueda de alguna manera a> valor de brecha elegido (O (log n))
Dependiendo de los datos, esto debería funcionar muy bien si los datos son enormes y vistos es escaso!
