सामान्य तौर पर, समय जटिलता और अंतरिक्ष जटिलता एक एल्गोरिदम की दक्षता को मापने के तरीके हैं जो इस पर आधारित हैं कि इसका संसाधन उपयोग किस प्रकार स्केल करता है इसके इनपुट का आकार. आइए बुनियादी बातों और कुछ सामान्य उदाहरणों पर गौर करें।

समय की जटिलता

समय जटिलता इनपुट के आकार (अक्सर n के रूप में चिह्नित) के आधार पर एक एल्गोरिदम को पूरा करने में लगने वाले समय की मात्रा का वर्णन करती है।

1. निरंतर समय - O(1):

   • एल्गोरिदम का निष्पादन समय इनपुट आकार के साथ नहीं बदलता है।
   • उदाहरण: किसी सरणी में किसी तत्व को अनुक्रमणिका द्वारा एक्सेस करना, जैसा कि arr[5] में है।

2. लॉगरिदमिक समय - ओ(लॉग एन):

   • जैसे-जैसे इनपुट का आकार बढ़ता है, एल्गोरिदम का निष्पादन समय लघुगणकीय रूप से बढ़ता है, जिसका अर्थ है कि यह प्रत्येक चरण के साथ समस्या को आधे में विभाजित करता है।
   • उदाहरण: क्रमबद्ध सरणी पर बाइनरी खोज।

3. रैखिक समय - O(n):

   • एल्गोरिदम का निष्पादन समय इनपुट आकार के साथ रैखिक रूप से बढ़ता है।
   • उदाहरण: n तत्वों की एक सरणी को एक बार पार करना।

4. रैखिक समय - O(n log n):

   • कुशल सॉर्टिंग एल्गोरिदम में आम है जहां प्रत्येक तत्व को लघुगणकीय रूप से नियंत्रित किया जाता है, आमतौर पर पुनरावर्ती विभाजन और रैखिक विलय या प्रसंस्करण के कारण।
   • उदाहरण: मर्ज सॉर्ट, क्विकसॉर्ट।

5. द्विघात समय - O(n²):

   • निष्पादन समय इनपुट आकार के वर्ग के अनुपात में बढ़ता है।
   • उदाहरण: नेस्टेड लूप, जैसे किसी सरणी में प्रत्येक तत्व की तुलना हर दूसरे तत्व से करना।

6. घन समय - O(n³):

   • निष्पादन समय इनपुट आकार के घन के साथ बढ़ता है। दुर्लभ लेकिन तीन नेस्टेड लूप वाले एल्गोरिदम में हो सकता है।
   • उदाहरण: ब्रूट-फोर्स एल्गोरिदम का उपयोग करके कुछ मैट्रिक्स संचालन को हल करना।

7. घातीय समय - O(2^n):

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

8. कारकीय समय - O(n!):

   • निष्पादन समय इनपुट आकार के साथ तथ्यात्मक रूप से बढ़ता है। अक्सर एल्गोरिदम से जिसमें सभी संभावित क्रमपरिवर्तन या संयोजन उत्पन्न करना शामिल होता है।
   • उदाहरण: ट्रैवलिंग सेल्समैन की समस्या को बलपूर्वक हल करना।

अंतरिक्ष जटिलता

अंतरिक्ष जटिलता इनपुट आकार के सापेक्ष एल्गोरिदम द्वारा उपयोग की जाने वाली मेमोरी की मात्रा को मापती है।

1. स्थिर स्थान - O(1):

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

2. लॉगरिदमिक स्पेस - ओ(लॉग एन):

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

3. रैखिक स्थान - O(n):

   • मेमोरी का उपयोग इनपुट आकार के साथ रैखिक रूप से बढ़ता है, जो इनपुट को संग्रहीत करने के लिए एक अतिरिक्त सरणी या डेटा संरचना बनाते समय आम है।
   • उदाहरण: n आकार की एक सरणी की एक प्रति बनाना।

4. द्विघात स्थान - O(n²):

   • मेमोरी का उपयोग इनपुट आकार के वर्ग के साथ बढ़ता है, जैसे कि nxn आकार के 2डी मैट्रिक्स को संग्रहीत करते समय।
   • उदाहरण: n नोड्स वाले ग्राफ़ के लिए एक आसन्न मैट्रिक्स संग्रहीत करना।

5. घातांकीय स्थान - O(2^n):

   • मेमोरी का उपयोग इनपुट आकार के साथ तेजी से बढ़ता है, अक्सर पुनरावर्ती समाधानों में जो इनपुट के प्रत्येक संभावित उपसमूह के लिए डेटा संग्रहीत करते हैं।
   • उदाहरण: कई अतिव्यापी उपसमस्याओं के साथ पुनरावर्ती एल्गोरिदम में संस्मरण।

व्यावहारिक उदाहरण

• रैखिक समय (O(n)) और रैखिक स्थान (O(n)):

  • एक फ़ंक्शन जो एक सरणी के माध्यम से पुनरावृत्त होता है और प्रत्येक तत्व को एक नई सरणी में संग्रहीत करता है।

• द्विघात समय (O(n²)) और स्थिर स्थान (O(1)):

  • एक फ़ंक्शन जिसमें एक सरणी पर दो नेस्टेड लूप होते हैं लेकिन कुछ वेरिएबल्स से परे अतिरिक्त भंडारण की आवश्यकता नहीं होती है।

जटिलता का विश्लेषण

समय और स्थान जटिलता के लिए कोड का विश्लेषण करते समय:

1. लूप की पहचान करें: नेस्टेड लूप आमतौर पर जटिलता बढ़ाते हैं (उदाहरण के लिए, एक लूप (O(n) ) देता है; दो नेस्टेड लूप (O(n^2) ) देते हैं)।
2. रिकर्सन की तलाश करें: रिकर्सिव कॉल शाखा कारक और रिकर्सन की गहराई के आधार पर घातीय समय और स्थान जटिलता को जन्म दे सकती है।
3. डेटा संरचनाओं पर विचार करें: सरणियों, सूचियों या हैश मानचित्रों जैसी अतिरिक्त डेटा संरचनाओं का उपयोग अंतरिक्ष जटिलता को प्रभावित कर सकता है।

सामान्य सुझाव

• समय जटिलता इनपुट आकार के एक फ़ंक्शन के रूप में संचालन की गिनती के बारे में है।
• अंतरिक्ष जटिलता आवश्यक अतिरिक्त मेमोरी की मात्रा की गणना करने के बारे में है।

इन कारकों का आकलन करके, आप अनुमान लगा सकते हैं कि एक एल्गोरिदम कितनी कुशलता से कार्य करता है और इनपुट आकार के आधार पर कितनी मेमोरी की खपत करता है।