3 सम

"3sum" redirects here. For the malt beverage, see Comparison of alcopops § Beer-based.

Unsolved problem in computer science:

Is there an algorithm to solve the 3SUM problem in time $O(n^{2-\epsilon })$, for some $\epsilon >0$?

(more unsolved problems in computer science)

कम्प्यूटेशनल जटिलता सिद्धांत में, 3SUM समस्या पूछती है कि क्या दिया गया सेट $n$ वास्तविक संख्याओं में तीन तत्व होते हैं जिनका योग शून्य होता है। एक सामान्यीकृत संस्करण, k-SUM, k संख्याओं पर समान प्रश्न पूछता है। 3SUM को आसानी से हल किया जा सकता है $O(n^{2})$ समय, और मिलान $\Omega (n^{\lceil k/2\rceil })$ गणना के कुछ विशेष मॉडलों में निचली सीमाएं ज्ञात होती हैं (Erickson 1999).

यह अनुमान लगाया गया था कि 3SUM के लिए किसी भी नियतात्मक एल्गोरिदम की आवश्यकता होती है $\Omega (n^{2})$ समय। 2014 में, मूल 3SUM अनुमान का एलन ग्रोनलुंड और सेठ पेटी ने खंडन किया था, जिन्होंने एक नियतात्मक एल्गोरिदम दिया था जो 3SUM को हल करता है $O(n^{2}/({\log n}/{\log \log n})^{2/3})$ समय। इसके अतिरिक्त, ग्रोनलुंड और पेटी ने दिखाया कि 3SUM की 4-निर्णय वृक्ष मॉडल#रैखिक निर्णय वृक्ष जटिलता है $O(n^{3/2}{\sqrt {\log n}})$. बाद में इन सीमाओं में सुधार किया गया। 3SUM के लिए वर्तमान सबसे प्रसिद्ध एल्गोरिदम चलता है $O(n^{2}(\log \log n)^{O(1)}/{\log ^{2}n})$ समय। केन, लवेट और मोरन ने दिखाया कि 6-निर्णय वृक्ष मॉडल#3SUM की रैखिक निर्णय वृक्ष जटिलता है $O(n{\log ^{2}n})$. बाद वाली सीमा कड़ी है (लघुगणकीय कारक तक)। यह अभी भी अनुमान लगाया गया है कि 3SUM का समाधान नहीं हो सका है $O(n^{2-\Omega (1)})$ अपेक्षित समय।

जब श्रेणी में तत्व पूर्णांक हों $[-N,\dots ,N]$, 3SUM में हल किया जा सकता है $O(n+N\log N)$ इनपुट सेट का प्रतिनिधित्व करके समय $S$ बिट सरणी के रूप में, सेट की गणना करना $S+S$ तेज फूरियर रूपांतरण का उपयोग करते हुए एक असतत कनवल्शन के रूप में सभी जोड़ीवार योगों की, और अंत में इस सेट की तुलना की गई $S$.

द्विघात एल्गोरिथ्म

मान लीजिए कि इनपुट ऐरे है $S[0..n-1]$. कंप्यूटिंग के पूर्णांक (शब्द रैम) मॉडल में, 3SUM को हल किया जा सकता है $O(n^{2})$ प्रत्येक संख्या डालने पर औसतन समय $S[i]$ एक हैश तालिका में, और फिर, प्रत्येक सूचकांक के लिए $i$ और $j$, जाँच कर रहा है कि हैश तालिका में पूर्णांक है या नहीं $-(S[i]+S[j])$.

कंप्यूटिंग या वास्तविक रैम के तुलना (कंप्यूटर प्रोग्रामिंग)-आधारित मॉडल में एक ही समय में समस्या को हल करना भी संभव है, जिसके लिए हैशिंग की अनुमति नहीं है। नीचे दिया गया एल्गोरिदम पहले इनपुट ऐरे को सॉर्ट करता है और फिर सावधानीपूर्वक सभी संभावित जोड़ियों का परीक्षण करता है, जिससे क्रमबद्ध सूची में जोड़ियों के लिए बाइनरी खोज की आवश्यकता से बचा जा सकता है, जिससे सबसे खराब स्थिति प्राप्त होती है। $O(n^{2})$ समय, इस प्रकार है. सॉर्ट(एस);

i = 0 से n - 2 के लिए करें
    ए = एस[आई];
    प्रारंभ = मैं + 1;
    अंत = एन - 1;
    जबकि (प्रारंभ <अंत) करते हैं
        बी = एस[प्रारंभ]
        सी = एस[अंत];
        यदि (ए + बी + सी == 0) तो
            आउटपुट ए, बी, सी;
            // शून्य के योग वाले सभी त्रिक संयोजनों की खोज जारी रखें।
            // हमें अंत और प्रारंभ दोनों को एक साथ अपडेट करने की आवश्यकता है क्योंकि सरणी मान अलग-अलग हैं।
            प्रारंभ = प्रारंभ + 1;
            अंत = अंत - 1;
        अन्यथा यदि (ए + बी + सी > 0) तो
            अंत = अंत - 1;
        अन्य
            प्रारंभ = प्रारंभ + 1;
    अंत
अंत

निम्नलिखित उदाहरण एक छोटे क्रमबद्ध सरणी पर इस एल्गोरिदम के निष्पादन को दिखाता है। ए के वर्तमान मान लाल रंग में दिखाए गए हैं, बी और सी के मान मैजेंटा में दिखाए गए हैं।

 -25 -10 -7 -3 2 4 8 10 (a +बी+सी==-25)
 -25 -10 -7 -3 2 4 8 10 (ए +बी+सी==-22)
 . . .
 -25 -10 -7 -3 2 4 8 10 (a +बी+सी==-7)
 -25 -10 -7 -3 2 4 8 10 (ए +बी+सी==-7)
 -25 -10 -7 -3 2 4 8 10 (ए +बी+सी==-3)
 -25 -10 -7 -3 2 4 8 10 (a +बी+सी==2)
 -25 -10 -7 -3 2 4 8 10 (a +बी+सी==0)

एल्गोरिथम की शुद्धता इस प्रकार देखी जा सकती है। मान लीजिए कि हमारे पास एक समाधान है a + b + c = 0. चूंकि सूचक केवल एक ही दिशा में चलते हैं, हम एल्गोरिदम को तब तक चला सकते हैं जब तक कि सबसे बाईं ओर का सूचक a की ओर इंगित न कर दे। एल्गोरिथम को तब तक चलाएँ जब तक कि शेष संकेतकों में से कोई एक b या c, जो भी पहले हो, को इंगित न कर दे। तब एल्गोरिथ्म तब तक चलेगा जब तक अंतिम सूचक सकारात्मक समाधान देते हुए शेष पद की ओर इशारा नहीं करता।

वेरिएंट

गैर-शून्य योग

उन संख्याओं की तलाश करने के बजाय जिनका योग 0 है, उन संख्याओं की तलाश करना संभव है जिनका योग कोई स्थिर सी है। पूर्णांक के लिए हैश तालिका खोजने के लिए मूल एल्गोरिदम को संशोधित करना सबसे आसान तरीका होगा $(C-(S[i]+S[j]))$.

दूसरी विधि:

• इनपुट सरणी के सभी तत्वों से C/3 घटाएँ।
• संशोधित सरणी में, 3 तत्व खोजें जिनका योग 0 है।

उदाहरण के लिए, यदि A=[1,2,3,4] और यदि आपको C=4 के लिए 3SUM खोजने के लिए कहा जाए, तो A के सभी तत्वों में से 4/3 घटाएं, और इसे सामान्य 3sum तरीके से हल करें, अर्थात। , $(a-C/3)+(b-C/3)+(c-C/3)=0$.

तीन अलग-अलग सरणियाँ

एक ही सारणी में 3 संख्याओं को खोजने के बजाय, हम उन्हें 3 अलग-अलग सारणियों में खोज सकते हैं। यानी, तीन सरणियाँ X, Y और Z दी गई हैं, तीन संख्याएँ खोजें a∈X, b∈Y, c∈Z, ऐसा है कि $a+b+c=0$. 1-सरणी वैरिएंट 3SUM×1 और 3-सरणी वैरिएंट 3SUM×3 को कॉल करें।

3SUM×1 के लिए एक सॉल्वर दिए जाने पर, 3SUM×3 समस्या को निम्नल�