एसिम्प्टोटिक सूचनाएं और एप्रीओरी विश्लेषण
एल्गोरिथ्म के डिजाइन में, एक एल्गोरिथ्म का जटिलता विश्लेषण एक अनिवार्य पहलू है। मुख्य रूप से, एल्गोरिदमिक जटिलता इसके प्रदर्शन के बारे में चिंतित है कि यह कितनी तेजी से या धीमी गति से काम करता है।
एक एल्गोरिथ्म की जटिलता डेटा और प्रसंस्करण समय को संसाधित करने के लिए आवश्यक मेमोरी की मात्रा के संदर्भ में एल्गोरिथ्म की दक्षता का वर्णन करती है।
एक एल्गोरिथ्म की जटिलता का दो दृष्टिकोणों में विश्लेषण किया गया है: Time तथा Space।
समय जटिलता
यह एक फ़ंक्शन है जो इनपुट के आकार के संदर्भ में एक एल्गोरिथ्म को चलाने के लिए आवश्यक समय की मात्रा का वर्णन करता है। "टाइम" का मतलब प्रदर्शन की गई मेमोरी एक्सेस की संख्या, पूर्णांकों के बीच तुलना की संख्या, कुछ आंतरिक लूप को निष्पादित करने की संख्या या वास्तविक समय की एल्गोरिथम की मात्रा से संबंधित कुछ अन्य प्राकृतिक इकाई होगी।
अंतरिक्ष की जटिलता
यह एक फ़ंक्शन है जो एल्गोरिथ्म में इनपुट के आकार के संदर्भ में एक एल्गोरिथ्म मेमोरी की मात्रा का वर्णन करता है। हम अक्सर "अतिरिक्त" मेमोरी की आवश्यकता की बात करते हैं, इनपुट को स्टोर करने के लिए आवश्यक मेमोरी की गिनती नहीं करते हैं। फिर, हम इसे मापने के लिए प्राकृतिक (लेकिन निश्चित-लंबाई) इकाइयों का उपयोग करते हैं।
अंतरिक्ष जटिलता को कभी-कभी नजरअंदाज कर दिया जाता है क्योंकि उपयोग की जाने वाली जगह न्यूनतम और / या स्पष्ट होती है, हालांकि कभी-कभी यह समय के रूप में महत्वपूर्ण मुद्दा बन जाता है।
असममित संकेतन
एल्गोरिथ्म का निष्पादन समय निर्देश सेट, प्रोसेसर गति, डिस्क I / O गति, आदि पर निर्भर करता है। इसलिए, हम एक एल्गोरिथ्म की दक्षता का अनुमान विषमता से लगाते हैं।
एक एल्गोरिथ्म के समय समारोह द्वारा दर्शाया गया है T(n), कहाँ पे n इनपुट आकार है।
एक एल्गोरिथ्म की जटिलता का प्रतिनिधित्व करने के लिए विभिन्न प्रकार के स्पर्शोन्मुख नोटेशन का उपयोग किया जाता है। एक एल्गोरिथ्म के चल रहे समय की जटिलता की गणना करने के लिए एसिम्प्टोटिक नोटेशन का उपयोग किया जाता है।
O - बिग ओह
Ω - बड़ा ओमेगा
θ - बिग थीटा
o - छोटे ओह
ω - थोड़ा ओमेगा
ओ: असममित ऊपरी बाउंड
'ओ' (बिग ओह) सबसे अधिक इस्तेमाल किया जाने वाला अंकन है। एक समारोहf(n) का प्रतिनिधित्व किया जा सकता है g(n) अर्थात् O(g(n)), यदि सकारात्मक पूर्णांक का मान मौजूद है n जैसा n0 और एक सकारात्मक स्थिरांक c ऐसा है कि -
$ f (n) \ leqslant cg (n) $ $ n> n_ {0} $ सभी मामले में
इसलिए, कार्य करें g(n) फ़ंक्शन के लिए एक ऊपरी बाध्य है f(n), जैसा g(n) से अधिक तेजी से बढ़ता है f(n)।
उदाहरण
आइए एक दिए गए फ़ंक्शन पर विचार करें, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $
$ G (n) = n ^ 3 $ को ध्यान में रखते हुए,
$ f (n) \ leqslant 5.g (n) $ n> 2 $ के सभी मूल्यों के लिए $
इसलिए, की जटिलता f(n) $ O (g (n)) $, यानी $ O (n ^ 3) $ के रूप में प्रतिनिधित्व किया जा सकता है
Pt: असममित निचला बाउंड
हम कहते हैं कि $ f (n) = \ Omega (g (n)) $ जब वहां मौजूद है c $ f (n) \ geqslant cg (n) $ सभी पर्याप्त रूप से बड़े मूल्य के लिए n। यहाँnएक सकारात्मक पूर्णांक है। इसका मतलब है फंक्शनg फ़ंक्शन के लिए एक कम बाध्य है f; के एक निश्चित मूल्य के बादn, f नीचे कभी नहीं जाएगा g।
उदाहरण
आइए एक दिए गए फ़ंक्शन पर विचार करें, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $।
$ G (n) = n ^ 3 $, $ f (n) \ geqslant 4.g (n) $ $ n> 0 $ के सभी मूल्यों को ध्यान में रखते हुए।
इसलिए, की जटिलता f(n) $ $ ओमेगा (जी (एन)) $, यानी $ \ ओमेगा (एन ^ 3) $ के रूप में प्रतिनिधित्व किया जा सकता है
pt: एसिम्प्टोटिक टाइट बाउंड
हम कहते हैं कि $ f (n) = \ theta (g (n)) $ जब स्थिरांक होते हैं c1 तथा c2 वह $ c_ {1} .g (n) \ leqllant f (n) \ leqslant c_ {2} .g (n) $ सभी पर्याप्त रूप से बड़े मूल्य के लिए। n। यहाँn एक सकारात्मक पूर्णांक है।
इसका मतलब है फंक्शन g कार्य के लिए एक तंग बाध्य है f।
उदाहरण
आइए एक दिए गए फ़ंक्शन पर विचार करें, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $
$ G (n) = n ^ 3 $, $ 4.g (n) \ leqslant f (n) \ leqslant 5.g (n) $ सभी बड़े मूल्यों को ध्यान में रखते हुए n।
इसलिए, की जटिलता f(n) $ $ थीटा (g (n)) $, यानी $ \ थीटा (n ^ 3) $ के रूप में प्रतिनिधित्व किया जा सकता है।
ओ - संकेतन
द्वारा प्रदान की गई स्पर्शोन्मुख ऊपरी सीमा O-notationasymptotically तंग नहीं हो सकता है या नहीं। बाध्य $ 2.n ^ 2 = O (n ^ 2) $ asymptotically तंग है, लेकिन बाध्य $ 2.n = O (n ^ 2) $ नहीं है।
हम प्रयोग करते हैं o-notation एक ऊपरी सीमा को निरूपित करने के लिए जो कि विषम रूप से तंग नहीं है।
हम औपचारिक रूप से परिभाषित करते हैं o(g(n)) (सेट के रूप में जी के छोटे-ओह) f(n) = o(g(n)) किसी भी सकारात्मक निरंतर $ c> 0 $ के लिए और वहां $ n_ {0}> 0 $ का मूल्य मौजूद है, जैसे कि $ 0 \ leqslant f (n) \ leqslant cg (n) $।
सहज रूप से, में o-notation, कार्यक्रम f(n) के सापेक्ष महत्वहीन हो जाता है g(n) जैसा nअनंतता; अर्थात्,
$ $ \ lim_ {n \ rightarrow \ infty} \ बाएँ (\ frac {f (n)} {g (n)} \ right) = 0 $ $
उदाहरण
आइए एक ही फ़ंक्शन पर विचार करें, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $
$ G (n) = n ^ {4} $ को देखते हुए,
$ $ \ lim_ {n \ rightarrow \ infty} \ बाएँ (\ frac {4.n ^ 3 + 10.n ^ 2 + 5.n + 1} {n ^ 4} \ right) = 0 $ $
इसलिए, की जटिलता f(n) $ o (g (n)) $, यानी $ o (n ^ 4) $ के रूप में प्रतिनिधित्व किया जा सकता है।
ation - संकेतन
हम प्रयोग करते हैं ω-notationएक निचली सीमा को निरूपित करने के लिए जो कि विषम रूप से तंग नहीं है। औपचारिक रूप से, हालांकि, हम परिभाषित करते हैंω(g(n)) (थोड़ा-ओ-जी के जी के) सेट के रूप में f(n) = ω(g(n)) किसी भी सकारात्मक निरंतर के लिए C > 0 और वहाँ एक मूल्य $ n_ {0}> 0 $ मौजूद है, जैसे कि $ 0 \ leqslant cg (n) <f (n) $।
उदाहरण के लिए, $ \ frac {n ^ 2} {2} = \ omega (n) $, लेकिन $ \ frac {n ^ 2} {2} \ neq \ omega (n ^ 2) $। संबंध $ f (n) = \ omega (g (n)) $ का तात्पर्य है कि निम्नलिखित सीमा मौजूद है
$ $ \ lim_ {n \ rightarrow \ infty} \ बाएँ (\ frac {f (n)} {g (n)} \ right) = \ infty $$
अर्थात्, f(n) के सापेक्ष बड़े पैमाने पर हो जाता है g(n) जैसा n अनंत तक पहुंचता है।
उदाहरण
आइए एक ही कार्य पर विचार करें, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $
$ G को ध्यान में रखते हुए (n) = n ^ 2 $,
$ $ \ lim_ {n \ rightarrow \ infty} \ बाएँ (\ frac {4.n ^ 3 + 10.n ^ 2 + 5.n + 1} {n ^ 2} \ right) = \ infty $ $
इसलिए, की जटिलता f(n) $ o (g (n)) $, यानी $ \ omega (n ^ 2) $ के रूप में प्रतिनिधित्व किया जा सकता है।
एप्रीओरी और अपोस्टियारी विश्लेषण
Apriori विश्लेषण का मतलब है, एक विशिष्ट प्रणाली पर इसे चलाने से पहले विश्लेषण किया जाता है। यह विश्लेषण एक ऐसा चरण है जहां कुछ सैद्धांतिक मॉडल का उपयोग करके फ़ंक्शन को परिभाषित किया जाता है। इसलिए, हम एल्गोरिथ्म को देखने के बजाय एक अलग मेमोरी, प्रोसेसर, और कंपाइलर के साथ किसी विशेष सिस्टम पर चलाने के बजाय समय और स्थान की जटिलता का निर्धारण करते हैं।
एक एल्गोरिथ्म के अपोस्टियारी विश्लेषण का मतलब है कि हम एक सिस्टम पर चलाने के बाद ही एक एल्गोरिथ्म का विश्लेषण करते हैं। यह सीधे सिस्टम पर निर्भर करता है और सिस्टम से सिस्टम में बदलाव करता है।
एक उद्योग में, हम Apostiari विश्लेषण नहीं कर सकते क्योंकि सॉफ्टवेयर आम तौर पर एक अनाम उपयोगकर्ता के लिए बनाया जाता है, जो इसे उद्योग में मौजूद लोगों से अलग एक प्रणाली पर चलाता है।
Apriori में, यही कारण है कि हम समय और स्थान की जटिलता को निर्धारित करने के लिए असममित नोटेशन का उपयोग करते हैं क्योंकि वे कंप्यूटर से कंप्यूटर में बदलते हैं; हालाँकि, asymptotically वे समान हैं।