एकाधिक नेस्टेड लूप के साथ बिग-ओ ढूँढना?

Question

int num = n/4; 
for (int i = 1; i <= num; i++) { 
    for (int j = 1; j <= n; j++) { 
     for (int k = 1; k <= n; k++) { 
      int count = 1; 
     } 
    } 
} 

मैंने जो पुस्तकें पढ़ी हैं, उनके अनुसार यह कोड ओ ((एन^3)/4 होना चाहिए)। लेकिन स्पष्ट रूप से यह नहीं है। नेस्टेड लूप के लिए बिग-ओ खोजने के लिए क्या आप सीमाओं को गुणा करना चाहते हैं? तो यह एक संख्या * एन * एन या एन/4 * एन * एन होना चाहिए।

Answer 1

O((n^3)/4) बड़े-ओ नोटेशन के मामले में कोई समझ नहीं आता है क्योंकि जटिलता को तर्क के अनुपात के रूप में मापने के लिए इसका मतलब है। 4 से विभाजित होने का कोई प्रभाव नहीं पड़ता है क्योंकि इससे अनुपात के मूल्य में परिवर्तन होता है लेकिन इसकी प्रकृति नहीं होती है।

ये सब बराबर हैं:

O(n^3) 
O(n^3/4) 
O(n^3*1e6) 

अन्य नियम केवल मतलब है जब वे इस तरह के रूप में एक n अवधि, शामिल हैं:

O(n^3/log(n)) 
O(n^3 * 10^n) 

एंथोनी Kanago ठीक ही बताते हैं के रूप में, यह करने के लिए सम्मेलन है:

• केवल शब्द को रकम के लिए उच्चतम वृद्धि दर के साथ रखें: O(n^2+n) = O(n^2) ।
• उत्पादों के लिए स्थिरांक से छुटकारा पाएं: O(n^2/4) = O(n^2)।

एक तरफ, मैं हमेशा सभी मामलों में उस पहले नियम से सहमत नहीं हूं। यह फ़ंक्शन की अधिकतम वृद्धि दर का निर्णय लेने के लिए एक अच्छा नियम है, लेकिन एल्गोरिदम तुलना ^(ए) जैसी चीजों के लिए जहां आप समझदारी से इनपुट पैरामीटर पर सीमा डाल सकते हैं, O(n^4+n^3+n^2+n) जैसे कुछ O(n^4) से काफी खराब है।

उस स्थिति में, कोई भी शब्द जो इनपुट पैरामीटर पर निर्भर करता है उसे शामिल किया जाना चाहिए। वास्तव में, यहां तक ​​कि स्थिर शब्द भी उपयोगी हो सकते हैं। उदाहरण के लिए O(n+1e100)O(n^2) के विरुद्ध तुलना करें - बाद में थोड़ी देर के लिए पूर्व को बेहतर प्रदर्शन करेगा, जब तक n कॉन्स्टेट शब्द पर प्रभाव डालने के लिए काफी बड़ा हो जाता है।

---

^(क) रहे हैं, ज़ाहिर है, जो उन लोगों के कहूँगा यह इस तरह से नहीं किया जाना चाहिए, लेकिन व्यावहारिकता अक्सर असली दुनिया में स्वमताभिमान पर काबू पा :-)

Answer 2

http://en.wikipedia.org/wiki/Big_O_notation से आप देख सकते हैं कि 1/4 जैसे स्थिरांक बिग-ओ नोटेशन को निर्धारित करने के लिए कोई भूमिका निभाते नहीं हैं। एकमात्र दिलचस्प तथ्य यह है कि यह एन^3 है, इस प्रकार ओ (एन^3)।

Answer 3

एक छोटी तकनीकीता। बिग ओ नोटेशन का उद्देश्य इनपुट के 'आकार' के संदर्भ में जटिलता का वर्णन करना है, न कि संख्यात्मक मूल्य। यदि आपका इनपुट एक संख्या है, तो इनपुट का आकार आपके नंबर के अंकों की संख्या है। हां, आपका एल्गोरिदम ओ (2^एन^3) है जिसमें एन अंकों की संख्या है।

More on this topic

Answer 4

औपचारिक रूप से, समय जटिलता की तरह निम्नलिखित निष्कर्ष निकाला जा सकता है: