Complexities (जटिलता)
एल्गोरिथम जटिलता (Algorithm Complexity) एक तरीका है एल्गोरिदम के प्रदर्शन को मापने का, जिसमें हम देखते हैं – कितना समय (Time Complexity) और इसके लिए कितनी मेमोरी (space) की आवश्यकता है|
1.Time Complexity (समय जटिलता) : समय जटिलता बताती है कि किसी समस्या को हल करने में किसी एल्गोरिथम को कितना समय लगता है।
- Why Important (क्यों महत्वपूर्ण) : एक कुशल एल्गोरिथम(Efficient Algorithm) चुनने में मदद करता है। इसका उपयोग बड़े इनपुट के लिए सर्वोत्तम समाधान तय करने के लिए किया जाता है।
- Example – Linear vs Binary Search
- Linear Search (रेखीय खोज) :
- हर एलिमेंट को एक-एक करके चेक करता है।
- सबसे खराब स्थिति(Worst Case) में बार-बार चेक करना पड़ सकता है।
- इसलिए इसकी समय जटिलता(Time Complexity) = O(n)
- Binary Search (द्विआधारी खोज) :
- सूची(List) को आधा-आधा बांटकर खोजें।
- चरण(Steps) बहुत कम लगे हैं (log₂n times)।
- Complexity = O(log n)
- बड़े डेटा पर बहुत तेजी से काम होता है।
2. Space Complexity (अंतरिक्ष जटिलता) – Space Complexity बताती है कि एल्गोरिथम को चलाने के लिए कितनी रैम चाहिए।
- मेमोरी का कई जगह उपयोग होता है:
- Input Variables: Data Store करने के लिए।
- Temporary Storage (अस्थायी भंडारण) : मध्यवर्ती (Intermediate परिणाम रखने के लिए।
- Program Instructions (प्रोग्राम निर्देश) : कोड(Code) स्वयं मेमोरी में स्टोर होता है।
- उदाहरण:
- Iterative Fibonacci (पुनरावृत्त फाइबोनैचि) : केवल दो Variables Use करता है → Space Complexity O(1)।
- Recursive Fibonacci (रिकर्सिव फाइबोनैचि) : हर Function Call Extra Stack Memory लेता है → Space Complexity O(n)।
Complexity का परिचय के लिए तीन Notations का उपयोग होता है:
- Big-O (O): Worst Case – Maximum Time/Space लगेगा।
- Big-Ω (Ω): Best Case – Minimum Time/Space लगेगा।
- Big-Θ (Θ): Average Case – Generally जितना लगेगा।
Example : Binary Search
- Best Case → Ω(1)
- Worst Case → O(log n)
- Average Case → Θ(log n)
Conclusion (निष्कर्ष)
- Time Complexity बताती है कि algorithm को input size n के लिए execution में कितना समय लगेगा।
- Space Complexity बताती है कि algorithm को input size n के लिए कितनी memory चाहिए।
- Efficient algorithms चुनने में यह दोनों metrics मदद करते हैं।
- Time-space tradeoff होता है: कभी कम समय के लिए ज्यादा memory, या कम memory में ज्यादा time।
- Complexity analysis से हम performance optimize कर सकते हैं और large inputs handle कर सकते हैं।
Important Questions and Answers
Q1. Time Complexity क्या है?
- यह measure है कि algorithm को input size n के लिए काम करने में कितना समय लगेगा।
Q2. Space Complexity क्या है?
- यह measure है कि algorithm को input size n के लिए कितना memory space चाहिए।
Q3. Best case, Worst case और Average case क्या होते हैं?
- Best case – जब algorithm सबसे कम time लेता है।
- Worst case – जब algorithm सबसे ज्यादा time लेता है।
- Average case – expected average time for random input.
Q4. O(1), O(n), O(n²) का मतलब क्या है?
- O(1) – Constant time, size बढ़ने पर भी same time
- O(n) – Linear time, size n के proportional
- O(n²) – Quadratic time, size n के square के proportional
Q5. Time-space tradeoff क्या है?
- कभी faster execution के लिए ज्यादा memory use होती है, या कम memory में ज्यादा time लगता है।
Q6. Recursion की time और space complexity कैसे होती है?
- Time – number of recursive calls × work per call
- Space – recursion stack memory + auxiliary space
