दो-सम - पूर्व-प्रकार अनुकूलन एल्गोरिथम डिजाइन

Nov 23 2020

C क्या आरोही या अवरोही क्रम में पूर्व-सॉर्ट किए गए इनपुट को प्राप्त करके दो-सम समाधान के रनटाइम को अनुकूलित करना संभव है?

Sum मूल दो-सम

निर्धारित करें कि क्या दो आइटम हैं जिनकी व्यक्तिगत क्षमता पूरी तरह से कुल क्षमता के बराबर होगी जबकि यह सुनिश्चित करना कि एक ही आइटम को दो बार नहीं चुना जा सकता है।

  • इनपुट: कुल क्षमता का प्रतिनिधित्व करने वाला इंट और इंट का प्रतिनिधित्व वस्तुओं की क्षमता का एक सरणी।
  • आउटपुट: एक बूलियन यह दर्शाता है कि कुल क्षमता को बराबर करने के लिए दो वस्तुओं के लिए संभव है या नहीं।
  • समय जटिलता: रैखिक विकास, $O(n)$
  • अंतरिक्ष की जटिलता: रैखिक विकास, $O(n)$

नमूने

इनपुट: [4, 5, 2, 6]

  • कुल क्षमता: 10
  • अपेक्षा: true

इनपुट: [4, 5, 2, 5]

  • कुल क्षमता: 10
  • अपेक्षा: true

इनपुट: [4, 5, 2, 7]

  • कुल क्षमता: 10
  • अपेक्षा: false

स्यूडोकोड

  1. searchSetउस आइटम को संग्रहीत करने के लिए एक सेट बनाएं जिसे पहले ही जांच लिया गया है।

  2. आइटम कैपेसिटी के इनपुट एरे के माध्यम से इरेट करें।

    2 ए। targetCapacityवर्तमान आइटम के लिए खोजें :totalCapacity - itemCapacity

    2 बी। यदि searchSetशामिल है targetCapacity, तो वापस लौटें true

    2c। वरना, जोड़ने itemCapacityके लिए searchSet

  3. falseअगर पूरा इनपुट बिना मैच पाए ही लौटा दिया जाए।

Sort पूर्व-क्रमबद्ध करें

  1. एक नया संस्करण सहेजें lastTargetCapacity
  2. यदि वर्तमान itemCapacity< lastTargetCapacity, कोई संभावित दो-रकम नहीं है और वापस लौटते हैं false

अर्थात

इनपुट: [6,2,1,0]

  • कुल क्षमता: 9

पुनरावृत्तियों

  1. targetCapacity = 9 - 6; lastTargetCapacity= ३
  2. itemCapacityकी 2< lastTargetCapacityकी वजह से झूठी वापसी करें 3

जवाब

AdamHurwitz Nov 28 2020 at 23:41

दो सम हल को रनटाइम प्रदर्शन के लिए अनुकूलित किया जा सकता है, यह देखते हुए कि इनपुट ऐरे को आरोही या अवरोही क्रम में पूर्व-सॉर्ट किया गया है।

यदि बाइनरी सर्च का उपयोग targetCapacityउपरोक्त को खोजने के लिए किया जाता है , तो यह लघुगणक में चलेगा,$O(logn)$, औसत रनटाइम। यह ऊपर के छद्मकोश से तेज है जो रैखिक में चलता है,$O(n)$, पुनरावृति और हैशिंग का उपयोग कर।

यदि छंटाई इनपुट में प्रदान नहीं की गई थी, तो छांटना और तेजी से खोजना संभव नहीं होगा $O(n)$। सबसे अच्छा जो किया जा सकता था$O(nlogn)$ क्विकॉर्ट और बाइनरी सर्च जैसी रणनीति के साथ।

देखें: स्टैनफोर्ड - दो सम स्पष्टीकरण

D.W. Nov 30 2020 at 12:46

हां, आप दो-योग समस्या को हल कर सकते हैं $O(n)$समय, यदि क्रमबद्ध क्रम में संख्याएँ प्रस्तुत की जाती हैं। इसे करने के लिए मेरा अन्य उत्तर देखें ; इसमें एक रैखिक स्कैन शामिल है। यह asymptotically इष्टतम है, क्योंकि यह पहले से ही लेता है$O(n)$ यहां तक ​​कि इनपुट को पढ़ने के लिए समय, और समस्या को हल करने के लिए पूरे इनपुट को पढ़ने की आवश्यकता हो सकती है, इसलिए आगे कोई असममित सुधार नहीं हो सकता है।