दो-सम - पूर्व-प्रकार अनुकूलन एल्गोरिथम डिजाइन
C क्या आरोही या अवरोही क्रम में पूर्व-सॉर्ट किए गए इनपुट को प्राप्त करके दो-सम समाधान के रनटाइम को अनुकूलित करना संभव है?
Sum मूल दो-सम
निर्धारित करें कि क्या दो आइटम हैं जिनकी व्यक्तिगत क्षमता पूरी तरह से कुल क्षमता के बराबर होगी जबकि यह सुनिश्चित करना कि एक ही आइटम को दो बार नहीं चुना जा सकता है।
- इनपुट: कुल क्षमता का प्रतिनिधित्व करने वाला इंट और इंट का प्रतिनिधित्व वस्तुओं की क्षमता का एक सरणी।
- आउटपुट: एक बूलियन यह दर्शाता है कि कुल क्षमता को बराबर करने के लिए दो वस्तुओं के लिए संभव है या नहीं।
- समय जटिलता: रैखिक विकास, $O(n)$
- अंतरिक्ष की जटिलता: रैखिक विकास, $O(n)$
नमूने
इनपुट: [4, 5, 2, 6]
- कुल क्षमता:
10 - अपेक्षा:
true
इनपुट: [4, 5, 2, 5]
- कुल क्षमता:
10 - अपेक्षा:
true
इनपुट: [4, 5, 2, 7]
- कुल क्षमता:
10 - अपेक्षा:
false
स्यूडोकोड
searchSetउस आइटम को संग्रहीत करने के लिए एक सेट बनाएं जिसे पहले ही जांच लिया गया है।आइटम कैपेसिटी के इनपुट एरे के माध्यम से इरेट करें।
2 ए।
targetCapacityवर्तमान आइटम के लिए खोजें :totalCapacity - itemCapacity2 बी। यदि
searchSetशामिल हैtargetCapacity, तो वापस लौटेंtrue।2c। वरना, जोड़ने
itemCapacityके लिएsearchSet।falseअगर पूरा इनपुट बिना मैच पाए ही लौटा दिया जाए।
Sort पूर्व-क्रमबद्ध करें
- एक नया संस्करण सहेजें
lastTargetCapacity - यदि वर्तमान
itemCapacity<lastTargetCapacity, कोई संभावित दो-रकम नहीं है और वापस लौटते हैंfalse।
अर्थात
इनपुट: [6,2,1,0]
- कुल क्षमता:
9
पुनरावृत्तियों
targetCapacity = 9 - 6;lastTargetCapacity= ३itemCapacityकी2<lastTargetCapacityकी वजह से झूठी वापसी करें3।
जवाब
दो सम हल को रनटाइम प्रदर्शन के लिए अनुकूलित किया जा सकता है, यह देखते हुए कि इनपुट ऐरे को आरोही या अवरोही क्रम में पूर्व-सॉर्ट किया गया है।
यदि बाइनरी सर्च का उपयोग targetCapacityउपरोक्त को खोजने के लिए किया जाता है , तो यह लघुगणक में चलेगा,$O(logn)$, औसत रनटाइम। यह ऊपर के छद्मकोश से तेज है जो रैखिक में चलता है,$O(n)$, पुनरावृति और हैशिंग का उपयोग कर।
यदि छंटाई इनपुट में प्रदान नहीं की गई थी, तो छांटना और तेजी से खोजना संभव नहीं होगा $O(n)$। सबसे अच्छा जो किया जा सकता था$O(nlogn)$ क्विकॉर्ट और बाइनरी सर्च जैसी रणनीति के साथ।
देखें: स्टैनफोर्ड - दो सम स्पष्टीकरण
हां, आप दो-योग समस्या को हल कर सकते हैं $O(n)$समय, यदि क्रमबद्ध क्रम में संख्याएँ प्रस्तुत की जाती हैं। इसे करने के लिए मेरा अन्य उत्तर देखें ; इसमें एक रैखिक स्कैन शामिल है। यह asymptotically इष्टतम है, क्योंकि यह पहले से ही लेता है$O(n)$ यहां तक कि इनपुट को पढ़ने के लिए समय, और समस्या को हल करने के लिए पूरे इनपुट को पढ़ने की आवश्यकता हो सकती है, इसलिए आगे कोई असममित सुधार नहीं हो सकता है।