क्या दो लूप (नेस्टेड) ​​के साथ एक एल्गोरिदम हो सकता है जैसे कि समग्र समय जटिलता ओ है (लॉग (लॉग एन))

यह निम्नलिखित को हल करने के बाद उत्पन्न हुआ:

for(i=N; i>0; i=i/2){
  for(j=0; j<i; j++){
    print "hello world"
  }
} 

उपरोक्त कोड में N की समय जटिलता है। (ज्यामितीय प्रगति की अवधारणा का उपयोग करना)। क्या समय जटिलता ओ (लॉग (लॉग एन)) के साथ समान लूप मौजूद हो सकता है?

1
Neel Alex 21 पद 2019, 21:04

1 उत्तर

सबसे बढ़िया उत्तर

एक लूप के लिए O(log log n) बार पुनरावृति करने के लिए, जहां लूप इंडेक्स वेरिएबल n तक गिना जाता है, फिर इंडेक्स वेरिएबल को लॉग के व्युत्क्रम फ़ंक्शन की तरह बढ़ना होगा लॉग k जहां k पुनरावृत्तियों की संख्या है; यानी इसे 2^2^k, या 2 के अलावा किसी अन्य आधार की तरह बढ़ना है।

इसे प्राप्त करने का एक तरीका यह है कि आप 2 से शुरू करें और n तक पहुंचने तक बार-बार वर्ग करें - यदि अनुक्रमणिका चर (((2^2)^2)...^2) के साथ है k वर्ग, तो यह आवश्यकता के अनुसार 2^2^k के बराबर होता है:

for(int i = 2; i < n; i = i*i) {
    //...
}

यह लूप आवश्यकतानुसार O(log log n) बार पुनरावृति करता है। यदि आप इसे नेस्टेड लूप के साथ बिल्कुल करना चाहते हैं, तो हम एक अतिरिक्त लूप जोड़ सकते हैं जो ओ (1) बार को पुनरावृत्त करता है, जिससे पुनरावृत्तियों की कुल संख्या समान रूप से समान होती है:

for(int i = 2; i < n; i = i*i) {
    for(int j = 0; j < 10; j++) {
        // ...
    }
}
4
kaya3 21 पद 2019, 22:00