एल्गोरिदम रनिंग टाइम ऑप्टिमाइज़ेशन

Question

मैं अपने एल्गोरिदम को अनुकूलित करने का एक तरीका ढूंढने की कोशिश कर रहा हूं जैसे कि चलने का समय ओ (एन²) (बिग ओ नोटेशन) है।

इनपुट केवल सकारात्मक और नकारात्मक पूर्णांक के एन तत्वों के साथ एक सरणी है। हम मान सकते हैं कि सरणी पहले से ही क्रमबद्ध है।

मुझे यह निर्धारित करना है: प्रत्येक आर (सरणी के तत्व) के लिए, चाहे आर = एस + टी, जहां एस और टी सरणी के तत्व भी हैं, और वही हो सकते हैं (एस == टी), या शून्य भी

मैंने जांच की है कि वर्तमान संख्या सकारात्मक या नकारात्मक है या नहीं, लेकिन चलने का समय अभी भी बहुत लंबा है या नहीं, मैंने जांच के लिए तत्वों की संख्या को कम करने की कोशिश की है। समस्या यह है कि मैं 3 का उपयोग कर रहा हूं जबकि लूप जो पहले से ही सबसे खराब मामले के लिए ओ (एन³) का चलने का मतलब है।

public static void Checker(int[] array) { 
    List<Integer> testlist = new ArrayList<Integer>(); 
    int i = 0; 
    while (i < array.length) { 
     int current = array[i]; 
     if (attached(current, array)) { 
      testlist.add(current); 
     } 
     i++; 
    } 
} 

public static boolean attached(int current, int[] array) { 
    boolean result = false; 
    int i = 0; 
    while (i < array.length && !result) { 
     int number1 = array[i]; 
     int j = 0; 
     while (j < array.length && !result) { 
      int number2 = array[j]; 
      if (number1 + number2 == current) { 
       result = true; 
      } 
      j++; 
     } 
     i++; 
    } 
    return result; 
} 

Answer 1

आप सरणी O(nlogn) (यदि नहीं) छँटाई शुरू कर सकते हैं, तो सरणी में प्रत्येक तत्व के लिए आप देख सकते हैं कि वहाँ दो तत्वों है कि योग O(n²) में संख्या के बराबर होती है है कर रहे हैं।

कोड सी # में है:

public static bool Solve(int[] arr) 
{ 
    Array.Sort(arr); //If not already sorted 

    foreach (var num in arr) 
     if (!FindTwoThatSumN(arr, num)) 
      return false; 

    return true; 
} 

public static bool FindTwoThatSumN(int[] arr, int num) 
{ 
    int min = 0; 
    int max = arr.Length - 1; 

    while (true) 
    { 
     if (min == max) break; 

     int sum = arr[min] + arr[max]; 

     if (sum < num) min++; 
     if (sum > num) max--; 
     if (sum == num) return true; 
    } 

    return false; 
} 

विचार अगर वहाँ एक सरणी में दोनों संख्याएं (अनुसार क्रमबद्ध किया जाना चाहिए) कि योग एक विशिष्ट मूल्य कम से कम (min = 0) से शुरू किया गया है और जांच करने के लिए अधिकतम (max = arr.Length), तो प्रत्येक चरण में:

• तो योग संख्या से कम है, min सूचकांक में वृद्धि।
• यदि राशि संख्या से अधिक है, तो max अनुक्रमणिका घटाएं।
• यदि योग संख्या के बराबर है, तो आपको एक समाधान मिलता है।
• यदि min सूचकांक max तक पहुंचता है तो कोई समाधान नहीं है।

आप अधिक जानकारी और सबूत के लिए इस question/answers का उल्लेख कर सकते हैं। समग्र समाधान के लिए

समय जटिलता O(n²) है:

• क्रमबद्ध सरणी: O(nlogn)।
• क्रमबद्ध सरणी पर Iterate: O(n)।
• मूल्य की संख्या दो अंक खोजें: O(n)।

तो, FindTwoThatSumN को नेस्टेड कॉल कारण O(n²) है।

यदि आप चाहते हैं कि आप अतिरिक्त संख्या से बचने के लिए FindTwoThatSumN विधि की बजाय इंडेक्स को पास कर सकें तो समाधान के हिस्से के रूप में स्वयं नंबर का उपयोग करें।

Answer 2

1. s + टी के सभी संभव रकम की गणना करने और अधिक एक सेट => O (n)
2. पुनरावृति में परिणाम रख:

   यहाँ मेरी कोड है प्रत्येक आर और जांच करें कि क्या कोई योग है जो => ओ (एन) से मेल खाता है क्योंकि set.contains निरंतर समय में चलता है।