एल्गोरिदम जटिलता

Question

मुझे यह समस्या मिली "किसी दिए गए सरणी में दो सबसे बड़ी संख्याओं के योग को वापस करने के लिए इस विधि को लागू करें।"

मैं इस तरह से इसका समाधान नहीं:

public static int sumOfTwoLargestElements(int[] a) { 

    int firstLargest = largest(a, 0, a.length-1); 

    int firstLarge = a[firstLargest]; 
    a[firstLargest] = -1; 

    int secondLargest = largest(a, 0, a.length-1); 

    return firstLarge + a[secondLargest]; 
} 

private static int largest(int s[], int start , int end){ 

    if (end - start == 0){ 

     return end; 
    } 


    int a = largest(s, start, start + (end-start)/2) ; 
    int b = largest(s, start + (end-start)/2+1 , end); 
    if(s[a] > s[b]) { 

     return a; 
    }else { 

     return b; 
    } 

} 

स्पष्टीकरण: मैं एक विधि 'largeset' लागू किया। यह विधि किसी दिए गए सरणी में सबसे बड़ी संख्या प्राप्त करने के लिए ज़िम्मेदार है।

मैं उसी सरणी में विधि टॉव टाइम्स को कॉल करता हूं। पहली कॉल को पहली सबसे बड़ी संख्या मिल जाएगी। मैंने इसे एक तरफ परिवर्तनीय रखा है और मैं इसे '-1' संख्या से सरणी में बदल देता हूं। फिर, मैं दूसरी बार सबसे बड़ा medhod बुलाओ।

कोई मुझे बता सकता है कि इस अलगो की जटिलता क्या है? कृपया

Answer 1

एल्गोरिदम की समय जटिलता O(n) है।

प्रत्येक पुनरावर्ती कॉल की जटिलता वास्तव में है:

f(n) = 2*f(n/2) + CONST 

यह देखना आसान है कि f(n) <= CONST'*n (प्रेरण द्वारा) है - और इस प्रकार यह O(n) है।

अंतरिक्ष जटिलता O(logN) है - क्योंकि यह रिकर्सन की अधिकतम गहराई है - इसलिए आप कॉल स्टैक पर O(logN) मेमोरी आवंटित करते हैं।

---

(1) आप का उपयोग करते हैं f(n) = 2*n*CONST - CONST आपको मिलेगा:

f(n) = 2*f(n/2) + CONST = (h.i.) 2*(2*CONST*n/2 - CONST) + CONST = 
= 2*n*CONST - 2CONST + CONST = 2*n*CONST - CONST 

Answer 2

एल्गोरिथ्म की जटिलता से मापा जा सकता है (आधार जाँच हो रही है पाठक के लिए व्यायाम के रूप में छोड़ दिया जाता है) O(n) के रूप में।

लेकिन असली जवाब यह है कि आपका एल्गोरिदम तरीका अधिक जटिल है, और मशीन संसाधनों के संदर्भ में अधिक महंगी होने की आवश्यकता है। और यह आपके कोड को पढ़ने और यह पता लगाने के मामले में यह अधिक महंगा है कि यह क्या कर रहा है।

अपने एल्गोरिथ्म की जटिलता वास्तव में के आदेश पर किया जाना चाहिए:

public static int sumOfTwoLargestElements(int[] a) { 

    //TODO handle case when argument is null, 
    //TODO handle case when array has less than two non-null elements, etc. 

    int firstLargest = Integer.MIN_VALUE; 
    int secondLargest = Integer.MIN_VALUE; 
    for (int v : a) { 
     if (v > firstLargest) { 
      secondLargest = firstLargest; 
      firstLargest = v; 
     } else if (v > secondLargest) secondLargest = v; 
    } 
    //TODO handle case when sum exceeds Integer.MAX_VALUE; 
    return firstLargest + secondLargest; 
} 

Answer 3

मेरे उद्देश्य हे (एन) की तुलना में कम जटिलता के साथ 'सबसे बड़ा' के लिए एक एल्गोरिथ्म को लागू करने की है। यही कारण है कि मैं लूप के लिए नहीं करना चाहता था। अपने जवाब :)

Answer 4

'सबसे बड़ा' विधि के लिए reccurence के लिए धन्यवाद है:

 _ 
f(n) = ! 
     ! 1  n = 1 
     ! 2f(n/2) n >=2 
     !_ 

If we experiment some few cases, we notice that 

f(n) = 2^log(n) When n is power of 2  Rq:Log base 2 

Proof: 

By induction, 

f(1) = 2^log(1) = 2^log(2^0) = 1 

We suppose that f(n) = 2^log(n)=n 

We show f(2n) = 2^log(2n)= 2n^log(2)=2n 

f(2n) = 2*f(2n/2) = 2*f(n) 
        = 2*2^log(n) 
        = 2^log(n) + 1 
        = 2^log(n) + log(2^0) 
        = 2^log(2n) 
        = 2n^log(2) by log properties 
        = 2n 
Then f(n) = 2^log(n)=n When n is power of2-smooth function f(2n) < c f(n). it follows smooth function properties that **f(n) = theta of n**