यह जानना अच्छा होगा कि हम किस तरह के डेटा की बात कर रहे हैं। कितने उपयोगकर्ता मौजूद हैं? औसतन कितने ऑनलाइन होंगे? सभी उपयोगकर्ताओं (विरल बनाम सघन) की तुलना में "देखे गए उपयोगकर्ताओं" का अनुपात कैसा है?
आपके एल्गोरिथम का संशोधन पहले पॉप न करें लेकिन ऑनलाइन उपयोगकर्ताओं के सेट से एक यादृच्छिक तत्व चुनें। इससे संतुलन में सुधार होना चाहिए और इन दो सेटों के अनुपात के आधार पर परिशोधित जटिलता में मदद मिल सकती है!
वैकल्पिक एल्गोरिथम (अधिक संरचित; फिर भी सबसे खराब स्थिति; यदि विरल देखा गया तो अच्छा होना चाहिए )
- देखे रखें एक संतुलित वृक्ष के रूप में (O(log n) सम्मिलन)
- ऑनलाइन रखें एक संतुलित वृक्ष के रूप में।
- जबकि पर्याप्त उपयोगकर्ता नहीं चुने गए:
- पहला अंतर देखा में खोजें (जैसे [0,1,3,7] -> 2; O(log n) SO-लिंक के अनुसार)
- पहले उपयोगकर्ता के लिए खोजें>=गैप-वैल्यू (O(log n))
- यदि उपयोगकर्ता
- -> चुनें
- अन्य
- -> चुने हुए अंतर-मान अस्थायी रूप से जोड़ें (इस पल के लिए; मॉडल-निर्णय कितनी बार ऑनलाइन को अपडेट करना है ) से देखा या खोज को किसी भी तरह> चुने हुए अंतराल-मान (O(log n))
. तक सीमित करें
डेटा के आधार पर, अगर डेटा बहुत बड़ा है और देखा है तो यह बहुत अच्छा काम करना चाहिए विरल है!
