बिग ओ नोटेशन निम्न नेस्टेड लूप के लिए क्या होगा?लॉग के 3 नेस्टेड लूप के जावा बिग ओ नोटेशन (एन)
for (int i = n; i > 0; i = i/2){
for (int j = n; j > 0; j = j/2){
for (int k = n; k > 0; k = k/2){
count++;
}
}
}
मेरे विचार कर रहे हैं: प्रत्येक पाश O(log2(n)) है तो यह रूप में सरल रूप में गुणा
O(log2(n)) * O(log2(n)) * O(log2(n)) = O(log2(n)^3)
हां, यह सही है।
नेस्टेड लूप की बड़ी-ओ जटिलता को समझने का एक तरीका जिसका सीमाएं तुरंत एक-दूसरे पर निर्भर नहीं होतीं, अंदरूनी ओर से काम करना है। Innermost पाश ओ (लॉग एन) काम करता है। दूसरा पाश ओ (लॉग एन) बार चलाता है और ओ (लॉग एन) प्रत्येक बार काम करता है, इसलिए यह ओ (लॉग n) काम करता है। अंत में, सबसे ऊपर लूप ओ (लॉग एन) बार चलाता है और ओ (लॉग एन) प्रत्येक पुनरावृत्ति पर काम करता है, इसलिए कुल कार्य किया जाता है ओ (लॉग n)।
आशा है कि इससे मदद मिलती है!
सही संकेत क्या है? ओ (लॉग 2 (एन)^3) या जिस तरह से आपके पास है? या वे दोनों स्वीकार्य हैं? –
मैंने इसे दोनों तरीकों से लिखा है। मैं व्यक्तिगत रूप से पाप^2 एक्स की शैली में लॉग^3 एन पसंद करता हूं, हालांकि संदर्भ में जो भी सम्मेलन प्रयोग किया जाता है, उसके साथ जाते हैं। – templatetypedef
ठीक है धन्यवाद! –
हाँ आप सही हैं। गणना करने के लिए
आसान तरीका -
for(int i=0; i<n;i++){ // n times
for(int j=0; j<n;j++){ // n times
}
}
सरल नेस्टेड लूप के इस उदाहरण। यहां प्रत्येक लूप ओ (एन) के बिग-ओ और यह आमतौर पर ओ (एन * एन) घोंसला है जो ओ (एन^2) वास्तविक बिग-ओ है। और अपने मामले में -
for (int i = n; i > 0; i = i/2){ // log(n)
for (int j = n; j > 0; j = j/2){ // log(n)
for (int k = n; k > 0; k = k/2){ // log(n)
count++;
}
}
}
कौन सा नेस्टेड पाश में है, जहां प्रत्येक पाश बिग-ओ है O(log(n)) इसलिए सभी को एक साथ जटिलता होगा O(log(n)^3)
दरअसल, अपने धारणा सही है। आपको निम्न रूप विधिपूर्वक यह दिखा सकते हैं:
मेरे धारणा भी होगा 'ओ (log2 (एन)^3)'। –