समय जटिलता()

Question

मैं इस समारोह power() जो दो तर्क और ले जाता है ab और एक ^ख गणना करता है कार्यान्वित किया।

typedef long long int LL; 

LL power(int a,int b) 
{ 
    int i = 1; 
    LL pow = 1; 
    for(; i <= b ; ++i) 
    pow *= a; 
    return pow; 
} 

को देखते हुए: एक ^खlong long int की रेंज में गिर जाता है।
समस्या: मेरे एल्गोरिदम की समय जटिलता को कैसे कम किया जाए?

Answer 1

स्क्वायरिंग द्वारा एक्सपोनेंटिएशन।

एक गैर पुनरावर्ती कार्यान्वयन

LL power(int a, int b) 
{ 
    LL pow = 1; 
    while (b) 
    { 
     if (b & 1) 
     { 
      pow = pow * a; 
      --b; 
     } 
     a = a*a; 
     b = b/2; 
    } 
    return pow; 
} 

इस एल्गोरिथ्म लॉग ख squarings और ज्यादा से ज्यादा लॉग ख गुणा की आवश्यकता है।

चलने का समय हे (लॉग ख)

---

Answer 2

उपयोग है Exponentiation by squaring

Answer 3

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

मनमाना परिशुद्धता के लिए: lib http://gmplib.org/manual/Integer-Exponentiation.html#Integer-Exponentiation

Answer 4

घातांक जीएमपी देखें squaring द्वारा सभी मामलों में गुणा की न्यूनतम संख्या नहीं देता है। "अतिरिक्त श्रृंखला", "ब्रायर चेन", "हैंनसेन चेन" और "स्कॉल्ज़ अनुमान" की तलाश करें।

Answer 5

वर्गों द्वारा एक्सपोनेंटिएशन का उपयोग करें। यही है अगर हमें^बी की आवश्यकता है, तो हम जांचें कि बी बी भी है, अगर बी भी है, तो हमें (a^2)^(b/2) मिल जाता है, अन्यथा हमें a*((a^2)^(b/2)) मिल जाएगा। यह सबसे अच्छा एल्गोरिदम नहीं हो सकता है, लेकिन यह रैखिक एल्गोरिदम से बेहतर है।

int Power(int a, int b) 
{ 
    if (b>0) 
    { 
     if (b==0) 
      return 1; 
     if (a==0) 
      return 0; 
     if (b%2==0) { 
      return Power(a*a, b/2); 
     } 
     else if (b%2==1) 
     { 
     return a*Power(a*a,b/2); 
     } 
    } 
    return 0; 
} 

Answer 6

यहाँ पुनरावर्ती हे के साथ की घात एन 2 के लिए जावा कोड के कार्यान्वयन (लॉग एन) जटिलता Exponentiation by squaring

int ans=1; 
public int myTwoPower(int n){ 
    if(n<=0) 
     return 1; 

    if(n%2 !=0){    
     return myTwoPower(n-1)*2; 
    } 
    else{ 
     ans = myTwoPower(n/2); 
     return ans * ans; 
    } 
}