सॉर्टिंग के साथ प्रस्तावित एक बनाम आपका दृष्टिकोण एक शास्त्रीय व्यापार-बंद प्रतीत होता है जिसमें संचालन सस्ता है और कौन सा महंगा है।
मैं अपने अंकन थोड़ा संशय है, तो मुझे मेरे हाल उपयोग करने की अनुमति दें:
S सेट होने दो। n सेट में आइटमों की संख्या होने दें: n = |S|। max सेट में सबसे बड़ी संख्या होने दें: max = max(S)। k सेट में मौजूद तत्वों की संख्या होने दें: k = |{0,...,max} \ S|।
सॉर्टिंग समाधान के लिए, हम हैशिंग का उपयोग करके n तत्वों को S में बहुत सस्ते रूप से सम्मिलित कर सकते हैं। यह O(n) की उम्मीद होगी। फिर k अनुपलब्ध तत्व ढूंढने के लिए, हम सेट को O(nlogn) में सॉर्ट करते हैं, और उसके बाद अनुपलब्ध तत्व O(n) में निर्धारित करते हैं।
n तत्व जोड़ने के लिए कुल लागत है और फिर अनुपलब्ध k तत्वों को O(n) + O(nlogn) + O(n) = O(nlogn) अपेक्षित लगता है।
आप एक अलग दृष्टिकोण है जिसमें हम S के घने सबसेट की एक सूची के रूप में सेट का प्रतिनिधित्व करते सुझाव देते हैं। आप इस तरह की डेटा संरचना कैसे कार्यान्वित करेंगे? मैं एक क्रमबद्ध पेड़ (एक सूची के बजाय) का सुझाव देता हूं ताकि एक सम्मिलन कुशल हो जाए। क्योंकि आपको एक नया तत्व e डालने के लिए क्या करना है? मुझे लगता है कि आपके पास करने के लिए:
- पेड़ जहां
e जोड़ा जा सकता है
- एक सबसेट पहले से ही
e मौजूद होता है तो में संभावित उम्मीदवार के सबसेट (रों) का पता लगाएं, कुछ भी नहीं किया जा सकता है।
- एक सबसेट
e+1 होता है और एक और सबसेट e-1 होता है, सबसेट एक साथ मर्ज और परिणाम
- तो एक सबसेट पहले से ही
e+1 शामिल करने के लिए e जोड़ने के लिए, लेकिन e-1S में निहित नहीं है, कि सबसेट के e जोड़ देते हैं तो
- एक सबसेट पहले से ही
e-1 शामिल है, लेकिन e+1S में निहित नहीं है, तो
- अन्यथा उस सबसेट को
e जोड़ने के लिए, एक नया सबसेट केवल तत्व e और डालने पकड़े बनाने यह पेड़ में।
हम उम्मीद कर सकते हैं कि उपरोक्त संचालन के लिए आवश्यक सबसेट ढूंढने से O(logn) लेता है। 4 या 5 के संचालन निरंतर समय लेते हैं यदि हम सबसेट्स के पूर्णांक के रूप में सबसेट का प्रतिनिधित्व करते हैं (हमें केवल ऊपरी सीमा में कमी या वृद्धि करना है)। 3. और 6. संभावित वृक्ष संरचना को बदलने की आवश्यकता होती है, लेकिन हम उस पर सबसे O(logn) अपनाए जाने की अपेक्षा है, तो पूरे "डालें" से अधिक नहीं O(logn) ले जाएगा।
अब इस तरह के डेटास्ट्रक्चर के साथ, हम आसानी से k पेड़ को पार करने और किसी भी सबसेट में संख्याओं को इकट्ठा करके गायब संख्या निर्धारित कर सकते हैं। लागत पेड़ है, जो <= n/2 है में नोड्स की संख्या में रेखीय हैं, इसलिए कुल लागत के लिए O(n) हैं।
हालांकि, अगर हम फिर से पूरा क्रम के संचालन पर विचार, हम n आवेषण O(nlogn) + O(n) कश्मीर संख्या लापता को खोजने के लिए के लिए मिलता है, तो कुल लागत फिर से O(nlogn) हैं।
यह पहली एल्गोरिथ्म की उम्मीद की लागत की तुलना में बेहतर नहीं है।
एक तिहाई समाधान एक बूलियन array उपयोग करने के लिए सेट और सेट में सबसे बड़ी तत्व के लिए एक एकल पूर्णांक max प्रतिनिधित्व करने के लिए है।
एक तत्व e सेट में जोड़ा जाता है, तो आप array[e] = true निर्धारित किया है। आप table expansion का उपयोग कर सेट के चर आकार को कार्यान्वित कर सकते हैं, इसलिए सरणी में तत्व डालने के लिए लागत स्थिर है।
गायब तत्वों को पुनर्प्राप्त करने के लिए, आप केवल उन तत्वों को f एकत्र करें जहां array[f] == false। इसमें O(max) लगेगा।
एन तत्वों को सम्मिलित करने और के गायब लोगों को खोजने के लिए कुल लागत इस प्रकार है: O(n) + O(max)। हालांकि, max = n + k, और इसलिए हम कुल लागत O(n + k) के रूप में प्राप्त करते हैं।
एक चौथाई विधि है जो एक क्रॉस ओवर तीसरे एक और एक है, जो भी हैशिंग का उपयोग करता है, लेकिन छँटाई की आवश्यकता नहीं है हैशिंग का उपयोग कर के बाद एक है के बीच।
अपने सेट S को हैश सेट में स्टोर करें, और S में अधिकतम तत्व को एक चर max में स्टोर करें। k गायब वाले लोगों को खोजने के लिए, पहले परिणाम सेट आर उत्पन्न करें जिसमें सभी नंबर {0,...,max} शामिल हैं। फिर S से अधिक सक्रिय करें और में R से प्रत्येक तत्व को हटाएं।
इसके लिए लागत भी O(n + k) है।
मुझे लगता है कि इसे गणित में पूछना बेहतर है। स्टैकएक्सचेंज, यह एक संयोजन समस्या –
समीकरण-आधारित उत्तरों के बजाय सीएस उत्तर है? ऐसा कुछ नहीं है। कम्प्यूटेशनल विधियों का उपयोग करके समीकरण हल किए जा सकते हैं। –
@Lior: [विडंबना] धन्यवाद, मुझे नहीं पता था! [विडंबना बंद] समीकरणों को विशिष्ट गणितीय ज्ञान की आवश्यकता होती है, क्योंकि आपको पहले यह जानना होगा कि आपका सिस्टम सुलभ होगा, और कौन सी संपत्ति कहा गया समीकरण बनाने के लिए उपयोग की जाती है, तो यह वास्तव में एक विशेष समाधान है (व्यक्तिगत रूप से मुझे इस तरह के समाधान के साथ आने के लिए कठोर दबाव डाला जाता था) यदि आपके पास बेहतर फॉर्मूलेशन है, तो मैं सवाल सुधारने के लिए तैयार हूं ... –