जावास्क्रिप्ट में ओ (एन^3) से ओ (एन^2) बदलना

Question

मैं अपने कोडिंग समाधान में समय बचाने के लिए अपने सिर को लपेटने की कोशिश कर रहा हूं।

मैं एक समारोह tripletSum कहा जाता है जो दो पैरामीटर x और a लेता है जहां x एक संख्या है और a एक सरणी है।

इस समारोह true वापस जाने के लिए करता है, तो सूची a तीन तत्व है जो संख्या x को जोड़ने में शामिल माना जाता है, अन्यथा यह false लौटना चाहिए।

मैं अगले कार्य समाधान बना लिया है:

function tripletSum(x, a) { 
    for(var i = 0; i < a.length; i++) { 
     for(var j = i + 1; j < a.length; j++) { 
      for(var k = j + 1; k < a.length; k++) { 
       if((a[i] + a[j] + a[k]) === x) { 
        return true; 
       } 
      } 
     } 
    } 
    return false; 
} 

लेकिन यह सबसे अच्छा अभ्यास की तरह प्रतीत नहीं होता। वर्तमान में इस फ़ंक्शन के माध्यम से चलाने में लगने वाला समय O(n^3) है यदि मुझे गलत नहीं लगता है और मुझे लगता है कि O(n^2) की समय जटिलता के लिए इसे बेहतर किया जा सकता है।

वैसे भी मैं यह कोड ऐसा करने के लिए बदल सकता हूं?

संपादित करें: यह अन्य प्रश्न का डुप्लिकेट नहीं है क्योंकि मैं जावास्क्रिप्ट में अपने वर्तमान उदाहरण पर एक विशिष्ट सुधार की मांग कर रहा था, जो कि चिह्नित डुप्लिकेट प्रश्न में नहीं पूछा गया था।

Answer 1

यहाँ विचार है: आप सरणी a को सॉर्ट करने के लिए सबसे पहले आवश्यकता है। इसके बाद आप एक लूप प्राप्त कर सकते हैं जो 0 से लेकर एन -2 (सभी विशेष रूप से) के सभी तत्वों के माध्यम से पुनरावृत्त हो जाता है। आइए इस लूप की अनुक्रमणिका i पर कॉल करें। यहां इस तथ्य की उपयोगिता आती है कि सरणी क्रमबद्ध है। हम ज्ञान का उपयोग करेंगे कि सरणी को "अप्रसन्न" उपन्यास (i + 1 से एन-वें तत्व तक) "निचोड़ने के लिए क्रमबद्ध किया गया है)। अब आपके पास 2 मान left और right होंगे। left अनप्रोसेस्ड सबएरे की बाएं इंडेक्स को इंगित करेगा, जबकि right सरणी के उस अनप्रचारित हिस्से का सही सूचकांक इंगित करेगा। शुरुआत में हम left = i + 1 और right = N - 1 सेट करते हैं। हम suma[i] + a[left] + a[right] की गणना करते हैं।अब हम 3 मामलों है:

1. If sum = x तो सच लौट तो हम योग कम करने की जरूरत है
2. तो sum > x, तो हम (दाएं से निचोड़) 1 से right घटती को
3. तो sum < x जरूरत है तो हम योग अधिक से अधिक करने की जरूरत है, तो हम (बाएं से निचोड़) 1 द्वारा left बढ़ाने के लिए

यहाँ जावास्क्रिप्ट समाधान इस प्रकार की जरूरत है।

function tripletSum(x, a) { 
    a.sort(function(i, j) { 
     return i - j; 
    }); 

    var N = a.length; 

    for(var i = 0; i < N - 2; i++) { 
     var left = i + 1, right = N - 1; 

     while(left < right) { 
      var sum = a[i] + a[left] + a[right]; 
      if(sum === x) { 
       return true; 
      } 
      else if(sum > x) { 
       right--; 
      } 
      else { 
       left++; 
      } 
     } 

    } 

    return false; 
} 

समय जटिलता O(N^2) है और कोई अतिरिक्त स्थान का उपयोग नहीं किया जा रहा है।

Answer 2

सरणी में निहित सभी कुंजी के लिए एक शब्दकोश-जैसी वस्तु रखें। फिर अपने दूसरे लूप में आप एक्स से दो मान घटाते हैं और अपने शब्दकोश में उस मान को देखते हैं।

function tripletSum(x, a) { 
    var dictionary = {}; 
    for(var i = 0; i < a.length; i++) { 
     dictionary[a[i]] = true; 
    } 

    for(var i = 0; i < a.length; i++) { 
     for(var j = i + 1; j < a.length; j++) { 
      var remainder = x - a[i] - a[j]; 
      if(dictionary[remainder]) 
       return true; 
     } 
    } 
    return false; 
} 

Answer 3

आप मूल रूप से हे से द्विआधारी खोज और एक तरह का उपयोग कर सकते हे करने के लिए जटिलता को कम करने के लिए (एन^2 * logn) (एन^3)।

function tripletSum(x, a) { 
 
    a.sort(function(a, b) { 
 
      return a - b 
 
     }) // O(n*logn) 
 
    var n = a.length; 
 
    for (var i = 0; i < n; i++) { 
 
     for (var j = i + 1; j < n; j++) { 
 
      if (a.indexOf(x - a[i] - a[j]) > j) { 
 
       return true; //O(n^2*logn) 
 
      } 
 
     } 
 
    } 
 
    return false; 
 
} 
 

 
console.log(tripletSum(0, [ 
 
    1, 
 
    5, 
 
    6, 
 
    -2, 
 
    -3 
 
]))

कुल जटिलता = O (n * logn) + O (n^2 * logn) ~ O (n^2 * logn)