इस ट्यूटोरियल में, आप सीखेंगे कि स्पर्शोन्मुख संकेतन क्या हैं। इसके अलावा, आप बिग-ओ नोटेशन, थीटा नोटेशन और ओमेगा नोटेशन के बारे में जानेंगे।
एक एल्गोरिथ्म की दक्षता एल्गोरिथ्म को निष्पादित करने के लिए आवश्यक समय, भंडारण और अन्य संसाधनों की मात्रा पर निर्भर करती है। दक्षता को स्पर्शोन्मुख संकेतन की मदद से मापा जाता है।
एक एल्गोरिथ्म में विभिन्न प्रकार के इनपुट के लिए समान प्रदर्शन नहीं हो सकता है। इनपुट आकार में वृद्धि के साथ, प्रदर्शन बदल जाएगा।
इनपुट आकार के क्रम में परिवर्तन के साथ एल्गोरिथ्म के प्रदर्शन में परिवर्तन के अध्ययन को स्पर्शोन्मुख विश्लेषण के रूप में परिभाषित किया गया है।
असममित संकेतन
असममित संकेतन गणितीय संकेतन होते हैं जिनका उपयोग एल्गोरिथ्म के चलने के समय का वर्णन करने के लिए किया जाता है जब इनपुट किसी विशेष मान या सीमित मान की ओर जाता है।
उदाहरण के लिए: बबल सॉर्ट में, जब इनपुट ऐरे को पहले से ही सॉर्ट किया जाता है, तो एल्गोरिथ्म द्वारा लिया गया समय रैखिक होता है यानी सबसे अच्छा मामला।
लेकिन, जब इनपुट सरणी रिवर्स स्थिति में होती है, तो एल्गोरिथ्म तत्वों को छाँटने के लिए अधिकतम समय (द्विघात) लेता है यानी सबसे खराब स्थिति।
जब इनपुट एरे को न तो क्रमबद्ध किया जाता है और न ही रिवर्स ऑर्डर में, तो औसत समय लगता है। इन अवधि को स्पर्शोन्मुख संकेतन का उपयोग करके दर्शाया जाता है।
मुख्य रूप से तीन स्पर्शोन्मुख संकेतन हैं:
- बिग-ओ संकेतन
- ओमेगा संकेतन
- थीटा संकेतन
बिग-ओ नोटेशन (ओ-नोटेशन)
बिग-ओ नोटेशन एक एल्गोरिथ्म के चलने के समय की ऊपरी सीमा का प्रतिनिधित्व करता है। इस प्रकार, यह एक एल्गोरिथ्म की सबसे खराब स्थिति जटिलता देता है।
बिग-ओ एक फ़ंक्शन की ऊपरी सीमा देता है
O (g (n)) = (f (n): वहाँ सकारात्मक स्थिरांक c और n 0 मौजूद हैं जैसे 0 ≦ f (n) n cg (n) सभी n 0 n 0 के लिए )
उपरोक्त अभिव्यक्ति को एक फ़ंक्शन के रूप में वर्णित किया जा सकता f(n)है O(g(n))यदि कोई सकारात्मक स्थिरांक मौजूद है, तो cयह पर्याप्त रूप से बड़े के लिए 0और इसके बीच स्थित है ।cg(n)n
किसी भी मूल्य के लिए n, एल्गोरिथ्म का चलने का समय उसके द्वारा दिए गए समय को पार नहीं करता है O(g(n))।
चूंकि यह एल्गोरिथम का सबसे खराब समय चल रहा है, इसलिए इसका उपयोग व्यापक रूप से एक एल्गोरिथ्म का विश्लेषण करने के लिए किया जाता है क्योंकि हम हमेशा सबसे खराब स्थिति में रुचि रखते हैं।
ओमेगा संकेतन (Ω-संकेतन)
ओमेगा संकेतन एक एल्गोरिथ्म के चलने के समय के निचले हिस्से का प्रतिनिधित्व करता है। इस प्रकार, यह एक एल्गोरिथ्म का सबसे अच्छा मामला जटिलता प्रदान करता है।
ओमेगा एक फ़ंक्शन के निचले हिस्से को देता है
) (जी (n)) = (f (n): वहाँ सकारात्मक स्थिरांक c और n 0 मौजूद हैं जैसे 0 (cg (n) (f (n) सभी n 0 n 0 के लिए )
उपरोक्त अभिव्यक्ति को एक फ़ंक्शन के रूप में वर्णित किया जा सकता f(n)है Ω(g(n))यदि कोई सकारात्मक स्थिरांक मौजूद है, तो cयह cg(n)पर्याप्त रूप से बड़े के लिए ऊपर स्थित है n।
किसी भी मूल्य के लिए n, एल्गोरिथ्म द्वारा आवश्यक न्यूनतम समय ओमेगा द्वारा दिया गया है Ω(g(n))।
थीटा संकेतन (Θ-संकेतन)
थीटा संकेतन ऊपर और नीचे से फ़ंक्शन को संलग्न करता है। चूंकि यह एल्गोरिथम के चलने के समय के ऊपरी और निचले हिस्से का प्रतिनिधित्व करता है, इसलिए इसका उपयोग एल्गोरिदम की औसत-केस जटिलता का विश्लेषण करने के लिए किया जाता है।
थीटा फंक्शन को कॉन्स्टेंट कारकों के भीतर बांधता है
एक समारोह के लिए g(n), Θ(g(n))संबंध द्वारा दिया जाता है:
) (G (n)) = (f (n): इसमें सकारात्मक स्थिरांक c 1 , c 2 और n 0 मौजूद हैं जैसे कि 0 that c 1 g (n) (f (n) 2 c 2 g (n) सभी के लिए एन 0 एन ० )
उपरोक्त अभिव्यक्ति को एक फ़ंक्शन के रूप में वर्णित किया जा सकता f(n)है Θ(g(n))यदि सेट में संबंधित है, तो सकारात्मक स्थिरांक मौजूद हैं और ऐसे कि यह पर्याप्त रूप से बड़े एन के लिए और बीच में सैंडविच हो सकता है ।c1c2c1g(n)c2g(n)
यदि कोई कार्य f(n)बीच में और सभी के लिए निहित है , तो इसे विषम रूप से तंग बाध्य कहा जाता है।c1g(n)c2g(n)n ≧ n0f(n)
