क्या सेट ए सेट का सबसेट है या नहीं, यह जांचने के लिए कोई एल्गोरिदम (अधिमानतः निरंतर समय) है?सेट ए के लिए एल्गोरिदम अगर सेट ए रैखिक समय से तेज़ में सेट बी का सबसेट है
इस समस्या को सुविधाजनक बनाने के लिए डेटा संरचनाएं बनाना रनटाइम के विरुद्ध नहीं गिना जाता है।
ठीक है, आपको A के प्रत्येक तत्व को देखना होगा, इसलिए यह A के आकार में कम से कम रैखिक समय होना चाहिए।
एक O(A+B) एल्गोरिथ्म hashtables का उपयोग कर आसान है (एक hashtable में B की दुकान तत्वों, तो A के प्रत्येक तत्व को देखने)। मुझे नहीं लगता कि आप तब तक बेहतर प्रदर्शन कर सकते हैं जब तक आप B के लिए कुछ अग्रिम संरचना नहीं जानते। उदाहरण के लिए, यदि B सॉर्ट किए गए क्रम में संग्रहीत है, तो आप बाइनरी खोज का उपयोग करके O(A log B) कर सकते हैं।
यदि आप दोनों को सेट करते हैं तो आप दो संग्रहों के मुख्य आइटम की तुलना कर सकते हैं। इस एल्गोरिदम का प्रदर्शन ओ (ए + बी) – Miguel
आप ब्लूम फ़िल्टर (http://en.wikipedia.org/wiki/Bloom_filter) के लिए जा सकते हैं। लेकिन वहाँ झूठे सकारात्मक है, जो विधि ऊपर कीथ ने उल्लेख द्वारा संबोधित किया जा सकता हो सकता है (लेकिन ध्यान दें कि हैशिंग की सबसे खराब स्थिति जटिलता हे (एन) नहीं है, लेकिन आप ओ (nlogn)।
है, मुझे यह एल्गोरिदम पसंद है क्योंकि कुछ पोस्ट प्रोसेसिंग मेरे मामले में बहुत तेज है। ब्लूम फ़िल्टर सर्वर पर चलाएगा और परिणाम सेट प्रोसेसिंग क्लाइंट साइड चलाएगा। – volni
करते देखें, तो आप कर सकते हैं अपने सेट को अपने कम से कम सामान्य अक्षरों और अक्षर जोड़े के साथ क्रमबद्ध करें और जितनी जल्दी हो सके नकारात्मक मैचों को फेंकने की संभावना को अधिकतम करें। यह मुझे स्पष्ट नहीं है कि यह एक ब्लूम फ़िल्टर के साथ कितना अच्छा होगा, शायद एक हैश टेबल करेगा क्योंकि बहुत सारे digrams और अक्षर नहीं हैं।
यदि आपके पास सबसेट्स के अधिकतम आकार या यहां तक कि एक सामान्य आकार के बारे में कुछ जानकारी थी, तो आप किसी दिए गए आकार के सभी सबसेट को एक ब्लूम फ़िल्टर में डालकर प्रीप्रोकैस डेटा कर सकते हैं।
आप इनमें से दोनों का संयोजन भी कर सकते हैं।
यह उत्तर मिला: http://stackoverflow.com/a/1338515/174674 – volni
हमें सेट सामग्री के बारे में अधिक जानकारी चाहिए। सामान्य एल्गोरिदम आपको स्थिर समय जटिलता नहीं देंगे। कम से कम, मुझे कोई नहीं पता। –
सेट तत्व तार हैं लेकिन निश्चित रूप से हम उन्हें कुछ हैश के माध्यम से चला सकते हैं या उन्हें बिट्ससेट में पदों को असाइन कर सकते हैं यदि इससे तेज एल्गोरिदम उत्पन्न होता है। – volni