👩🏻‍🤝‍👨🏾 🗂️ 👻 एल्गोरिथम अनुमान 🧑🏾‍🤝‍🧑🏼 ⛓️ 📥

परिचय

किसी भी प्रोग्रामर के लिए एल्गोरिदम के सिद्धांत की मूल बातें जानना महत्वपूर्ण है, क्योंकि यह यह विज्ञान है जो एल्गोरिदम की सामान्य विशेषताओं और उनके प्रतिनिधित्व के लिए औपचारिक मॉडल का अध्ययन करता है। यहां तक कि कंप्यूटर विज्ञान के पाठों से, हमें फ्लोचार्ट तैयार करना सिखाया जाता है, जो बाद में, स्कूल की तुलना में अधिक जटिल कार्यों को लिखने में मदद करता है। यह भी एक रहस्य नहीं है कि लगभग हमेशा एक विशेष समस्या को हल करने के कई तरीके होते हैं: कुछ में बहुत समय बिताना शामिल होता है, दूसरों के संसाधन, और अभी भी दूसरों को लगभग एक समाधान खोजने में मदद मिलती है।

आपको हमेशा कार्य के अनुसार इष्टतम की तलाश करनी चाहिए, विशेष रूप से, जब समस्याओं के वर्ग को हल करने के लिए एल्गोरिदम विकसित करना।
यह मूल्यांकन करना भी महत्वपूर्ण है कि एल्गोरिथ्म विभिन्न संस्करणों और मात्राओं के प्रारंभिक मूल्यों पर कैसे व्यवहार करेगा, इसके लिए किन संसाधनों की आवश्यकता होगी और अंतिम परिणाम के उत्पादन में कितना समय लगेगा।
यह एल्गोरिथ्म सिद्धांत के अनुभाग से निपटा गया है - एल्गोरिदम के एसिम्प्टोटिक विश्लेषण का सिद्धांत।

मैं इस लेख में मुख्य मूल्यांकन मानदंडों का वर्णन करने और सरलतम एल्गोरिथ्म के मूल्यांकन का एक उदाहरण देने का प्रस्ताव करता हूं। एल्गोरिदम के मूल्यांकन के तरीकों के बारे में पहले से ही हब्राह पर एक लेख है, लेकिन यह मुख्य रूप से हाई स्कूल के छात्रों के लिए है। इस प्रकाशन को उस लेख का विस्तार माना जा सकता है।

परिभाषित

एल्गोरिथ्म की जटिलता का मुख्य संकेतक समस्या को हल करने के लिए आवश्यक समय और आवश्यक स्मृति की मात्रा है।
इसके अलावा, जब कार्यों के एक वर्ग के लिए जटिलता का विश्लेषण करते हैं, तो एक निश्चित संख्या निर्धारित की जाती है जो डेटा की एक निश्चित राशि की विशेषता है - इनपुट का आकार ।
तो, हम यह निष्कर्ष निकाल सकते हैं कि एल्गोरिथ्म की जटिलता इनपुट आकार का एक कार्य है।
एल्गोरिथ्म की जटिलता एक ही इनपुट आकार के साथ भिन्न हो सकती है, लेकिन विभिन्न इनपुट डेटा।

सबसे खराब , मध्यम या सर्वश्रेष्ठ मामले में जटिलता की अवधारणाएं हैं। आमतौर पर, सबसे खराब स्थिति जटिलता का आकलन किया जाता है।

सबसे खराब स्थिति में, समय जटिलता एक आकार के एक समस्या को हल करते समय एल्गोरिथ्म के संचालन के दौरान किए गए अधिकतम संचालन के बराबर इनपुट आकार का एक कार्य है।
सबसे खराब स्थिति में, कैपेसिटिव जटिलता एक इनपुट आकार का एक फ़ंक्शन है जो किसी भी आकार की समस्याओं को हल करते समय अधिकतम पहुंच गई मेमोरी कोशिकाओं के बराबर है।

एल्गोरिथम विकास क्रम

जटिलता वृद्धि (या स्वयंसिद्ध जटिलता) का क्रम एक बड़े इनपुट आकार के साथ एल्गोरिथ्म की जटिलता फ़ंक्शन के अनुमानित व्यवहार का वर्णन करता है। यह इस प्रकार है कि समय की जटिलता का आकलन करते समय प्राथमिक कार्यों पर विचार करने की आवश्यकता नहीं है, यह एल्गोरिथ्म के चरणों पर विचार करने के लिए पर्याप्त है।

एल्गोरिथ्म का चरण क्रमिक रूप से स्थित प्राथमिक संचालन का एक सेट है, जिसका निष्पादन समय इनपुट के आकार पर निर्भर नहीं करता है, अर्थात, यह कुछ निरंतर द्वारा ऊपर से घिरा हुआ है।

स्पर्शोन्मुख अनुमानों के प्रकार

ओ - सबसे खराब स्थिति

जटिलता f (n)> 0 , समान क्रम g (n)> 0 , इनपुट आकार n> 0 के एक कार्य पर विचार करें।
यदि f (n) = O (g (n)) और स्थिरांक हैं c> 0 , n ₀ > 0 , तब
0 <f (n) <c * g (n),
n> n _{0 के लिए} ।

इस मामले में फ़ंक्शन जी (एन) एफ (एन) का एक असममित रूप से सटीक अनुमान है। यदि f (n) एल्गोरिथम की जटिलता का एक कार्य है, तो जटिलता के क्रम को f (n) - O (g (n)) के रूप में परिभाषित किया गया है।

यह अभिव्यक्ति फ़ंक्शंस के एक वर्ग को परिभाषित करती है जो निरंतर कारक तक जी (एन) से अधिक तेज़ी से नहीं बढ़ती है।

स्पर्शोन्मुख कार्यों के उदाहरण

च (n)	जी (एन)
2 एन ² + 7 एन - 3	एन ^२
98 एन * एलएन (एन)	n * ln (n)
5 एन + 2	n
8	1

Best - सबसे अच्छा मामला स्कोर

परिभाषा, हालांकि सबसे खराब स्थिति स्कोर की परिभाषा के समान है
f (n) = Ω (g (n)) अगर
0 <c * g (n) <f (n)

Ω (g (n)) फ़ंक्शंस के एक वर्ग को परिभाषित करता है जो फंक्शन g (n) की तुलना में धीमी गति से बढ़ता है एक स्थिर कारक तक।

। - औसत मामले के लिए स्कोर

यह उल्लेखनीय है कि इस मामले में n> n _{0 के} लिए फ़ंक्शन f (n) c ₁ * g (n) और c ₂ * g (n) के बीच हर जगह है, जहाँ c एक स्थिर कारक है।
उदाहरण के लिए, f (n) = n ² + n के साथ ; g (n) = एन ² ।

एल्गोरिथम मूल्यांकन मानदंड

एक समान भार मानदंड (आरवीसी) मानता है कि एल्गोरिथ्म के प्रत्येक चरण को समय की एक इकाई में, और मेमोरी सेल को एक इकाई की मात्रा (एक स्थिर तक) में किया जाता है।
लॉगरिदमिक वेटिंग मानदंड (LCV) ऑपरेंड के आकार को ध्यान में रखता है, जो एक विशेष ऑपरेशन और मेमोरी सेल में संग्रहीत मूल्य से संसाधित होता है।

एलसीवी का समय जटिलता एल (ओ _पी ) के मूल्य से निर्धारित होता है, जहां ओ _पी ऑपरेंड का मूल्य है।
एलसीवी की कैपेसिटिव जटिलता एल (एम) के मूल्य से निर्धारित होती है, जहां एम मेमोरी सेल का आकार है।

तथ्यात्मक गणना करते समय जटिलता मूल्यांकन का उदाहरण

फैक्टरियल की गणना के लिए एल्गोरिथ्म की जटिलता का विश्लेषण करना आवश्यक है। ऐसा करने के लिए, हम भाषा C के छद्म पृष्ठ पर इस कार्य को लिखते हैं:

void main() { int result = 1; int i; const n = ...; for (i = 2; i <= n; i++) result = result * n; }

समान वजन मापदंड के साथ समय की जटिलता

यह निर्धारित करना काफी सरल है कि इस कार्य का इनपुट आकार n है ।
चरणों की संख्या है (n - 1) ।

इस प्रकार, RVC के लिए समय जटिलता O (n) है ।

एक लघुगणकीय वजन कसौटी के साथ समय जटिलता

इस अनुच्छेद को उन कार्यों को उजागर करना चाहिए जिनका मूल्यांकन करने की आवश्यकता है। सबसे पहले, ये तुलनात्मक संचालन हैं। दूसरे, बदलते चर (जोड़, गुणा) का संचालन। असाइनमेंट ऑपरेशन को ध्यान में नहीं रखा जाता है, क्योंकि यह माना जाता है कि यह तुरंत होता है।

इसलिए, इस कार्य में, तीन ऑपरेशन प्रतिष्ठित हैं:

1) मैं <= एन

Ith कदम पर, हम लॉग (n) प्राप्त करते हैं ।
चूंकि चरण (एन -1) हैं , इस ऑपरेशन की जटिलता (एन -1) * लॉग (एन) होगी ।

2) i = i + 1

Ith कदम पर, हम लॉग (i) प्राप्त करते हैं ।
इस प्रकार, योग

।

3) परिणाम = परिणाम * मैं

I-th स्टेप पर, हम लॉग ((i-1)!) प्राप्त करते हैं ।
इस प्रकार, योग

।

यदि हम सभी परिणामी मूल्यों को जोड़ते हैं और उन शब्दों को त्याग देते हैं जो स्पष्ट रूप से बढ़ते हुए n के साथ धीरे-धीरे बढ़ते हैं, तो हमें अंतिम अभिव्यक्ति मिलती है

।

समान वजन मापदंड के साथ कैपेसिटिव जटिलता

यहां सब कुछ सरल है। चर की संख्या गिनना आवश्यक है। यदि सरणियों का उपयोग कार्य में किया जाता है, तो सरणी में प्रत्येक सेल को एक चर माना जाता है।
चूँकि चरों की संख्या इनपुट के आकार पर निर्भर नहीं करती है, जटिलता O (1) होगी ।

एक लघुगणकीय वजन कसौटी के साथ कैपेसिटिव जटिलता

इस स्थिति में, अधिकतम मान जो मेमोरी सेल में हो सकता है। यदि मान परिभाषित नहीं किया गया है (उदाहरण के लिए, ऑपरेंड i> 10 के साथ), तो यह माना जाता है कि कुछ सीमा मान V _{अधिकतम है} ।
इस समस्या में, एक चर है जिसका मान n (i) से अधिक नहीं है, और एक चर जिसका मान n से अधिक नहीं है ! (परिणाम) । इस प्रकार, स्कोर ओ (लॉग (एन!)) है ।

निष्कर्ष

एल्गोरिदम की जटिलता का अध्ययन करना एक आकर्षक काम है। फिलहाल, सरलतम एल्गोरिदम का विश्लेषण कंप्यूटर विज्ञान में शामिल तकनीकी विशेषताओं ("कंप्यूटर विज्ञान और कंप्यूटर इंजीनियरिंग" की सामान्यीकृत दिशा) के सटीक होने के लिए, आईटी के क्षेत्र में लागू गणित में शामिल है।
जटिलता के आधार पर, कार्यों के विभिन्न वर्गों को प्रतिष्ठित किया जाता है: पी , एनपी , एनपीसी । लेकिन यह अब एल्गोरिदम के स्पर्शोन्मुख विश्लेषण के सिद्धांत की समस्या नहीं है।

एल्गोरिथम अनुमान