लूप के साथ प्रतिनिधित्व लॉगरिदमिक जटिलता? - एल्गोरिदम, जटिलता-सिद्धांत, बड़ा-ओ

जहां तक ​​मुझे यह मिला है कि रैखिक जटिलता को सरल लूप के रूप में दर्शाया जा सकता है और द्विघात जटिलता को नेस्टेड लूप के रूप में दर्शाया जा सकता है। घन और लघुगणक जटिलता का प्रतिनिधित्व कैसे किया जा सकता है?

धन्यवाद!

उत्तर:

एक साधारण लूप में लॉगरिदमिक जटिलता हो सकती है, उदा।

for (i = 1; i <= N; i *= 2)
...

जैसा कि अन्य पहले ही उत्तर दे चुके हैं, ट्रिपल नेस्टेड लूप में क्यूबिक जटिलता होगी।

क्यूंकि क्यूबिक हे (n ^ 3) है, यह तीन नेस्टेड लूप होगा।

लॉगरिदमिक इतना सीधा और आमतौर पर नहीं हैएक पुनरावर्ती संबंध की आवश्यकता है। उदाहरण के लिए, MergeSort O (n * log (n)) है क्योंकि यह ऊँचाई लॉग (n) का पुनरावर्तन ट्री बनाता है और प्रत्येक स्तर के लिए O (n) मर्जिंग ऑपरेशन की आवश्यकता होती है।

घन जटिलता - दो नेस्टेड छोरों:

foreach
foreach
foreach
// actions
end
end
end

लघुगणक जटिलता उदाहरण - द्विआधारी खोज.

• क्यूबिक - तीन नेस्टेड लूप्स
• लॉगरिदमिक - प्रत्येक लूप चक्र पर विचारआप भागों द्वारा निर्धारित इनपुट डेटा को विभाजित कर रहे हैं (या किसी तरह इसे छोटा बनाता है) और अगले चक्र की प्रक्रिया में डेटा सेट को छोटा कर दिया है, इसलिए मूल रूप से जटिलता में वृद्धि नहीं होती है जबकि इनपुट डेटा सेट में वृद्धि होती है। उदाहरण के लिए पर एक नज़र रखना बाइनरी सर्च एल्गोरिथ्म या कोई अन्य विभाजन और जीत कलन विधि।

O (n ^ 3) को 3 नेस्टेड लूप द्वारा दर्शाया जा सकता है।

O (लॉग एन) को एक लूप द्वारा दर्शाया जाता है जो प्रत्येक पुनरावृत्ति, संसाधित किए जाने वाले डेटा की मात्रा को आधे से कम करता है।