बिग ओ

Question

को समझना निम्नलिखित कोड को देखते हुए 3. की जटिलता क्या है और मैं निम्नलिखित जटिलताओं के साथ सरल एल्गोरिदम का प्रतिनिधित्व कैसे करूं?

ओ (n² + एन)
ओ (n² + 2n)
ओ (logn) ओ (nlogn)

var collection = new[] {1,2,3}; 
var collection2 = new[] {1,2,3}; 

//1. 
//On 
foreach(var i in c1) 
{ 
} 

//2. 
//On² 
foreach(var i in c1) 
{ 
    foreach(var j in c1) 
    { 
    } 
} 

//3. 
//O(nⁿ⁺ᵒ)? 
foreach(var i in c1) 
{ 
    foreach(var j in c2) 
    { 
    } 
} 

Answer 1

बाहरी foreach n निष्पादित किया जाता है = | c1 | बार (जहां | x | c1 का आकार है), जबकि आंतरिक foreach निष्पादित किया गया है m = | c2 | बार। कुल मिलाकर ओ (एन * एम) बार है।

---

मैं निम्नलिखित जटिलताओं के साथ सरल एल्गोरिदम कैसे प्रतिनिधित्व करेंगे?

• ओ (n² + n)

यह O (n^2) के समान है। कुछ ऐसा जो ओ (एन^2) समय लेता है, पार्टी में हर दूसरे व्यक्ति के साथ एक टोस्ट पीता है, यह मानते हुए कि टोस्ट में हमेशा दो लोग रहते हैं, और केवल एक ही व्यक्ति एक समय में टोस्टिंग करता है।

• ओ (n² + 2n) ऊपर के रूप में

एक ही; ओ (एन^2) शब्द हावी है। ओ (एन^2) प्रयास का एक और उदाहरण लंबाई n के वर्ग के बगीचे में वृक्ष लगा रहा है, मानते हुए कि प्रत्येक पेड़ को लगाने के लिए लगातार समय लगता है, और एक बार जब आप पेड़ लगाते हैं तो अन्य पेड़ों को इसके आसपास से बाहर रखा जाता है।

• ओ (logn)

इस का एक उदाहरण बार-बार पृष्ठों को आप अगले खोज करने की आवश्यकता के क्षेत्र के मध्य को चुनकर शब्दकोश में एक शब्द की खोज की जाएगी। (दूसरे शब्दों में, एक द्विआधारी खोज।)

• ओ (nlogn)

उपरोक्त एल्गोरिथ्म का उपयोग करें, लेकिन अब आप शब्दकोश में हर शब्द लगाना होगा।

Answer 2

3 है O (n * मी), या O (n^2) यदि दो संग्रह एक ही आकार के हैं। क्योंकि n n^2 से छोटी है

O (n^2 + एन) व्यर्थ है। बस ओ लिखें (एन^2)।

अधिकांश सभ्य comparison sort एल्गोरिदम हे पर चलाने (एन * लॉग (एन))। यदि आप किसी को नहीं जानते हैं, तो विकिपीडिया देखें।

एक binary search हे है (लॉग (एन))।

Answer 3

3 की जटिलता हे (एम * एन) है। कोई जटिलता हे है (एन + n) या O (n + 2n)।यह सिर्फ ओ (एन) है। ऐसा इसलिए है क्योंकि एन ओ (एन) है।

ओ (लॉग (एन)) का उदाहरण बाइनरी खोज है।

ओ (एन * लॉग (एन)) का उदाहरण विलय प्रकार है।

Answer 4

कोई ओ (एन² + एन) या ओ (एन^2 + 2 एन) नहीं है। एल्गोरिदमिक जटिलता की अधिकांश गणितीय नींव को छोड़कर, आपको कम से कम यह जानना होगा कि यह "एम्पिप्टोटिक" है। चूंकि एन अनंतता तक पहुंचता है, एन^2 + एन का मान एन^2 शब्द का प्रभुत्व है, इसलिए यह एन^2 + एन की एसिम्प्टोटिक जटिलता है।

3 की जटिलता ओ (आई * जे) है, जहां मैं और जे सी 1 और सी 2 में इनपुट का आकार हैं।

Answer 5

सत्य को बताया जाना चाहिए ओ (एन² + एन) & ओ (एन² + 2 एन) वही हैं।