2 अलग-अलग सरणी में तत्वों के सभी जोड़ों को तुरंत कैसे प्राप्त करें

Question

इसलिए हाल ही में मैंने इस प्रोग्रामिंग समस्या पर हमला किया जो मुझे जटिलता कम नहीं कर सका (मेरा वर्तमान कोड ओ (एन^2) में चलता है)।

अनिवार्य रूप से, मेरे पास चार अलग-अलग सूचियां हैं (मैं पाइथन बीटीडब्लू का उपयोग कर रहा हूं) सकारात्मक और नकारात्मक दोनों, सूचियों ए, बी, सी, डी। अब, इनमें से प्रत्येक सूची में 1000 पूर्णांक हैं, और इन पूर्णांक -25000 से 25000 समावेशी तक है। अब, इन सूचियों में से प्रत्येक से मान लें कि हम एक पूर्णांक चुनते हैं, ए, बी, सी, डी कहते हैं। मैं इन ए, बी, सी, डी को खोजने का सबसे तेज़ तरीका चाहूंगा कि एक + बी = - (सी + डी)।

वर्तमान में, मेरी विधि ए, बी, और सी, डी के प्रत्येक संभावित संयोजन के माध्यम से फिर से स्थापित करने पर निर्भर करती है, यह निर्धारित करने की कोशिश कर रही है कि सेट में कोई तत्व सेट (ए + बी) सेट में मौजूद है - (सी + घ)। यह, ज़ाहिर है, यह अव्यवहारिक है क्योंकि यह ओ (एन^2) समय में चलता है, और भी बड़ी सूची आकार (1000) पर विचार करता है।

इसलिए मैं सोच रहा था कि कोई भी अधिक कुशल तरीके से सोच सकता है (अधिमानतः ओ (एन लॉग एन) या छोटा), यदि संभव हो तो पाइथन में कोडित।

क्षमा करें अगर यह भ्रमित है। यदि आपके कोई प्रश्न हैं तो कृपया मुझे सूचित करें, मैं और स्पष्टीकरण प्रदान करने की कोशिश करूंगा।

संपादित करें:

यह समस्या एक बड़ी समस्या का हिस्सा है। बड़ी समस्या बताती है कि यदि हमारे पास प्रत्येक में अधिकतम 1000 पूर्णांक वाले संख्याओं के 4 अनुक्रम हैं, तो ए, बी, सी, डी कहें, ए, बी, सी, डी जैसे कि + बी + सी + डी = 0 खोजें।

मैंने उपरोक्त प्रश्न पूछा क्योंकि एक + बी + सी + डी = 0 का तात्पर्य है कि एक + बी = - (सी + डी), जो मैंने सोचा था कि समस्या को हल करने का सबसे तेज़ तरीका होगा। अगर कोई भी तेज़ तरीका सोच सकता है, तो कृपया इसे मेरे साथ साझा करें।

अग्रिम धन्यवाद! :)

Answer 1

आपकी समस्या यह नहीं है कि तत्वों के जोड़ों को जोड़ना ओ (एन^2) है, बल्कि यह तथ्य कि आप दो ऐसी प्रक्रियाओं को एक ओ (एन^4) एल्गोरिदम के साथ समाप्त करने के लिए नैतिक रूप से संयोजित कर रहे हैं। मुझे लगता है कि आपको बस 0 को जोड़ने के लिए> = 1 तरीके खोजने की आवश्यकता है - नीचे दी गई मेरी विधि को सभी तरीके खोजने के लिए आसानी से बढ़ाया जा सकता है, यदि आवश्यक हो।

को देखते हुए आप स्वीकार किए जाते हैं, मानों की एक अपेक्षाकृत संकीर्ण सीमा है (+ 25k के लिए -25k, चलो उन MIN और MAX क्रमशः कॉल), यहाँ आप क्या करना है:

बनाएं आकार के 2 पूर्णांक सरणियों (मैक्स - मिन + 1), "इंडेक्सए" और "इंडेक्सबी"। यह स्मृति के 0.5 एमबी भी एक साथ नहीं है, इसलिए आधुनिक प्रणाली पर चिंता करने के लिए कुछ भी नहीं है।

अब सूची ए और बी के सभी तत्वों पर लूप, जैसा कि आप कर रहे थे।इस छद्म कोड की तरह कुछ करो (अजगर के साथ भी परिचित नहीं तो मुझे यकीन है कि अगर यह वैध है नहीं कर रहा हूँ के रूप में है):

for idxA, valA in enumerate(A): 
    for idxB, valB in enumerate(B): 
     indicesA[valA + valB - MIN] = idxA + 1 
     indicesB[valA + valB - MIN] = idxB + 1 

अब जब पर पाशन सिर्फ एक हे (1) देखने की मेज के रूप में उपयोग बी और सी:

for valC in C: 
    for valD in D: 
     neededVal = -(valC + valD) - MIN 
     if indicesA[neededVal] > 0: 
      print('Found solution: {0} {1} {2} {3}'.format(A[indicesA[neededVal] - 1], 
       B[indicesB[neededVal] - 1], valC, valD)) 

• 0s के साथ लुक-तालिका प्रारंभ: हे (मैक्स - मिन) (~ 50, एन^2 इस मामले में की तुलना में छोटे)
• एक पर पाशन द्वारा भरने देखने की मेज और बी: ओ (एन^2)
• सी और डी और चे पर लूपिंग किसी भी समाधान के लिए cking: ओ (एन^2)

कुल मिलाकर, ओ (एन^2 + (MAX - MIN)) = ~ ओ (एन^2) दिए गए मानों के साथ। शायद उससे बेहतर नहीं कर सकते हैं।