मैं एराटोस्टेनेस एल्गोरिदम समय जटिलता की चलनी को समझने की कोशिश कर रहा हूं। हर जगह ऑनलाइन, यह कहता है कि समय जटिलता ओ (nloglog (एन)) है, लेकिन मुझे समझ में नहीं आता क्यों।एरेटोस्टेनेस एल्गोरिदम के चलनी की समय जटिलता क्यों तर्क sqrt (n) है?
यहाँ कुछ स्यूडोकोड
factors = new int[n+1];
for i from 2 to n
factors[i] = 1; //true
for i from 2 to sqrt(n)
if(factors[i] == 1) //isPrime
{
for all multiples of i upto n
factors[multiple] = 0 //notPrime
}
return all indices of factors that have a value of 1
मुझे लगता है कि हम सभी इस बात से सहमत कर सकते हैं कि इस समारोह के समय जटिलता पाश के लिए नेस्टेड पर निर्भर करता है। अब इसका विश्लेषण। जब मैं = 2, आंतरिक पाश एन/2 बार चलाता है। जब मैं = 3, आंतरिक पाश एन/3 बार चलाता है। अगली बार जब आंतरिक लूप निष्पादित होता है तो अगला प्राइम नंबर एन/5 गुना होता है। कुल मिलाकर पाश चलेंगे
n/2 + n/3 + n/5 + n/7 + ... बार
यह वह जगह है
n (1/2 + 1/3 + 1/5 + 1/7 + ...)
एन के प्राइम के पारस्परिक गुणों का योग ओ (लॉग (लॉग (एन)) का तत्व है)। इस प्रकार, समग्र जटिलता ओ (नलॉग (लॉग (एन)) है
हाउवर, जैसा कि हमारे छद्म कोड में लिखा गया है, लूप के लिए बाहरी केवल रूट (एन) बार चलाता है। इस प्रकार हम केवल sqrt (एन) तक primes के पारस्परिक संबंधों को संक्षेप में जोड़ रहे हैं। तो जटिलता होनी चाहिए (nlog (लॉग (sqrt (n)))) ऊपर वर्णित नहीं है।
मेरे विश्लेषण में क्या गलत है?