Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में समय जटिलता विश्लेषण पर अभ्यास प्रश्न


समय जटिलता किसी भी एल्गोरिदम को पूरा करने में लगने वाला समय है। यह एल्गोरिदम की दक्षता दिखाने और तुलनात्मक विश्लेषण के लिए एक महत्वपूर्ण मीट्रिक है। हम एल्गोरिदम की समय जटिलता को कम करने का प्रयास करते हैं जो इसे अधिक प्रभावी बनाता है।

उदाहरण 1

निम्नलिखित कोड स्निपेट्स की समय जटिलता खोजें

for(i= 0 ; i < n; i++){    cout<< i << " " ;    i++; }

लूप का अधिकतम मान n है लेकिन i फोर लूप में दो बार इंक्रीमेंट होगा जिससे समय आधा हो जाएगा। तो समय जटिलता O(n/2) है जो O(n) के बराबर है।

उदाहरण 2

निम्नलिखित कोड स्निपेट्स की समय जटिलता खोजें

for(i= 0 ; i < n; i++){    for(j = 0; j<n ;j++){       cout<< i << " ";    } }

आंतरिक लूप और बाहरी लूप दोनों n बार निष्पादित हो रहे हैं। तो i के एकल मान के लिए, j n बार लूप कर रहा है, i के n मानों के लिए, j कुल n*n = n 2 बार लूप करेगा। तो समय जटिलता O(n 2 ) है।

उदाहरण 3

निम्नलिखित कोड स्निपेट्स की समय जटिलता खोजें

int i = n; while(i){    cout << i << " ";    i = i/2; }

इस मामले में, प्रत्येक पुनरावृत्ति के बाद i का मान उसके पिछले मान का आधा हो जाता है। तो श्रृंखला इस तरह होगी: . तो समय जटिलता O(log n) है।

उदाहरण 4

निम्नलिखित कोड स्निपेट्स की समय जटिलता खोजें

if(i > j ){    j>23 ? cout<<j : cout<<i; }

कोड में दो सशर्त कथन हैं। प्रत्येक सशर्त कथन की समय जटिलता = O(1), उनमें से दो के लिए यह O(2) है जो O(1) के बराबर है जो कॉन्स्टेंट है।

उदाहरण 5

निम्नलिखित कोड स्निपेट्स की समय जटिलता खोजें

for(i= 0; i < n; i++){    for(j = 1; j < n; j = j*2){       cout << i << " ";    } }

आंतरिक लूप (log n) बार निष्पादित हो रहा है जहां बाहरी n बार निष्पादित हो रहा है। तो i के एकल मान के लिए, j (log n) बार निष्पादित हो रहा है, i के n मानों के लिए, j कुल n*(log n) = (n log n) बार लूप करेगा। तो समय जटिलता O(n log n) है।


  1. एमोर्टाइज़्ड कॉम्प्लेक्सिटी (परिशोधित जटिलता) एमोर्टाइज़्ड कॉम्प्लेक्सिटी (परिशोधित जटिलता)

    एमोर्टाइज़्ड एनालिसिसयह विश्लेषण तब उपयोग किया जाता है जब कभी-कभार होने वाला ऑपरेशन बहुत धीमा होता है, लेकिन अधिकांश ऑपरेशन जो बहुत बार निष्पादित होते हैं, वे तेज़ होते हैं। डेटा संरचनाओं में हमें हैश टेबल, डिसजॉइंट सेट आदि के लिए एमोर्टाइज़्ड विश्लेषण की आवश्यकता होती है।हैश टेबल में, अधिकांश समय स

  1. एसिम्प्टोटिक कॉम्प्लेक्सिटी (आशय जटिलता) एसिम्प्टोटिक कॉम्प्लेक्सिटी (आशय जटिलता)

    एसिम्प्टोटिक एनालिसिसएसिम्प्टोटिक विश्लेषण का उपयोग करके, हम इनपुट आकार के आधार पर एल्गोरिदम के प्रदर्शन के बारे में एक विचार प्राप्त कर सकते हैं। हमें सटीक रनिंग टाइम की गणना नहीं करनी चाहिए, बल्कि रनिंग टाइम और इनपुट आकार के बीच संबंध ढूंढना चाहिए। हमें रनिंग टाइम का पालन करना चाहिए जब इनपुट का आक

  1. C/C++ में बर्कले का एल्गोरिथ्म C/C++ में बर्कले का एल्गोरिथ्म

    बर्कले का एल्गोरिथ्म वितरित प्रणालियों में क्लॉक सिंक्रोनाइज़ेशन के लिए उपयोग किया जाने वाला एक एल्गोरिथ्म है। यह एल्गोरिथ्म उन मामलों में उपयोग किया जाता है जब वितरित नेटवर्क के कुछ या सभी सिस्टम में निम्नलिखित समस्याएं होती हैं: A. मशीन के पास सटीक समय स्रोत नहीं है। B. नेटवर्क या मशीन के पास UTC