Big O Notation – Complexity of Data Structure

Big O Notation – दो Algorithms में से कौनसा Algorithm अधिक Efficient है ये Analyze करने के लिए हमें दोनों Algorithms से प्राप्त होने वाले Results को Compare करना होता है। हम दो Algorithms से प्राप्त होने वाले Results को Compare कर सकें इसके लिए हमें “O” Notation को जानना जरूरी है।

कोई Algorithm कितने Operations करने के बाद Required काम को पूरा करता है, ये जानने के लिए हम कुछ Standard Function का प्रयोग करते हैं जो कि निम्नानुसार हैं-

      log2 n        n          n log2 n     n2        n3        2n

ये सभी Functions ¼ फलन ½ किसी Algorithm का आयाम ज्ञात करने के लिए Use होते हैं। यानी n2 से n3 का आयाम अधिक होता है। यदि कोई एक Algorithm n2 Operations के बाद हमें Required Results प्रदान करता है जबकि दूसरा Algorithm n3 Operations के बाद हमें Required Result Provide करता है, तो पहले वाले Algorithm से दूसरा वाला Algorithm अधिक Complex होगा। ये सभी Function एक निश्चित क्रम के अनुसार Input Data n के लिए आयाम प्रदान करते हैं।

विभिन्न Functions जो आयाम प्रदर्शित करते हैं उन सभी आयाम प्रदर्शित करने वाले Functions को Handle करने के लिए एक Notation को Develop किया गया है। एक Function f(n) को O(g(n)) के रूप में परिभाद्गिात किया जा सकता है। यानी इसे f(n) = O(g(n)) लिख सकते हैं और इस फलन को g(n) का क्रम कहा जाता है।

यानी यदि निम्नानुसार n0 c Positive Constant हों-

| f(n) | <= | g(n) | जबकि सभी n > n0

तो हम इसे “O” Notation के अनुसार लिख सकते हैं। जैसे निम्न फलनों का “O” Notation निम्नानुसार लिखा जा सकता है-


100 n5                                              का “O” Notation O(n5) होगा।
200n3 + 50n2 + 20n1 + 544n0                          का “O” Notation O(n3) होगा।
1 + 2 +  . . .  + (n-1) + n = n(n+1)/2 = n2 + O(n)  का “O” Notation O(n2) होगा।
3223                                                का “O” Notation O(1) या O(n) होगा।

सरल शब्दों में कहें तो हम कह सकते हैं कि O(g) फलनों (Functions) का एक ऐसा समूह होता है जो कि g के आधार पर Increase या Grow होता है जहां फलन g फलन O(g) का Upper Bound है।

हम O(g) के विभिन्न फलनों के आधार पर विभिन्न Algorithms की Complexity ज्ञात कर सकते हैं और दो अलग-अलग Algorithms की Efficiency की आपस में तुलना करके पता लगा सकते हैं कि कौनसा Algorithm अधिक Efficient या कम Complex है। ये फलन Computer या Programming Language पर निर्भर नहीं होते हैं

इसलिए किसी Algorithm को बिना Implement किए हुए यानी Algorithm के आधार पर बिना Program बनाए हुए ही इन फलनों द्वारा हम ये जान सकते हैं कि कोई Algorithm कितना Complex है।

Time Analysis in Data Structure
Properties of Big “O” Notation

Data Structure and Algorithmes in Hindiये Article इस वेबसाईट पर Selling हेतु उपलब्‍ध EBook Data Structure and Algorithms in Hindi से लिया गया है। इसलिए यदि ये Article आपके लिए उपयोगी रहा, तो निश्चित रूप से ये पुस्तक भी आपके लिए काफी उपयोगी साबित होगी। 

Data Structure and Algorithms in Hindi | Page: 433 | Format: PDF

BUY NOW DOWNLOAD READ ONLINE

Special Discount Offer

खरीदिए एक से ज्‍यादा EBooks, और पाईए ₹100 से ₹1200 तक का Extra Cash Discount

Discount Coupon Codes