जांच करें कि प्रधानमंत्री बड़े-ओ

Question

मेरे मूल कार्य निर्धारित करने के लिए एक नंबर प्रधानमंत्री था:

bool is_prime(int x) { 
    for (int y = 2; y < x; ++y) { 
     if (x % y == 0) { 
      return false; 
     } 
    } 
    return true; 
} 

यह O(x) की जटिलता के साथ भाग गया के रूप में आप x पर जाने के लिए हो सकता था।

मैंने कुछ अनुकूलन के बारे में सीखा है और मेरे बड़े-ओ पर एक चेक की आवश्यकता है। यहाँ बेहतर कार्यक्रम है:

bool is_prime(int x) 
{ 
    if (x % 2 == 0 && x > 2) { 
     return false; 
    } 
    for (int y = 3; y*y <= x; y += 2) { 
     if (x % y == 0) { 
      return false; 
     } 
    } 
    return true; 
} 

तथ्य यह है कि मैं अब तक sqrt() परिवर्तन को यह O(sqrt(x)) करने जा रहा हूँ करता है?

Answer 1

हां, लेकिन यहां कोई n एस नहीं है। आपके नए फ़ंक्शन की जटिलता ओ (वर्ग (x)) है। जब आप ओ (एन) निर्दिष्ट करते हैं और यह निर्दिष्ट नहीं करते कि एन है, तो इसे आम तौर पर इनपुट के आकार माना जाता है। यह उन कार्यों के लिए भ्रमित है जो एक संख्या संख्या तर्क लेते हैं, इसलिए उन मामलों में आपको स्पष्ट होना चाहिए।

Answer 2

बिल्कुल, अपने नए समारोह की जटिलता

ओ (sqrt (एक्स))

लेकिन फिर भी, वहाँ अनुकूलन के लिए कुछ कमरे है। नीचे उल्लिखित कोड पर एक नज़र डालें:

bool isPrime(int n) 
{ 
    // Boundary cases 
    if (n <= 1) return false; 
    if (n <= 3) return true; 

    // This is checked so that we can skip 
    // middle five numbers in below loop 
    if (n%2 == 0 || n%3 == 0) return false; 

    for (int i=5; i*i<=n; i=i+6) 
     if (n%i == 0 || n%(i+2) == 0) 
      return false; 

    return true; 
}