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)
