एल्गोरिदम और उनकी जटिलता का विश्लेषण कैसे करें

एल्गोरिदम लगभग सभी कार्यों में शामिल होता है जो हम दैनिक आधार पर करते हैं। हम उनमें से कई को "स्वचालित" पर निष्पादित करते हैं, यहां तक ​​कि "क्या" का उपयोग किए बिना उन्हें "या" हम कैसे उपयोग करते हैं, यह भी महसूस किए बिना। सॉफ्टवेयर विकास में, यह अलग नहीं है। लेकिन, एल्गोरिदम वैसे भी क्या हैं? और उनकी जटिलता का विश्लेषण करना क्यों महत्वपूर्ण है?

चलो पता करते हैं! :)

एक एल्गोरिथ्म क्या है?

किसी कार्य को करने के लिए आवश्यक चरणों का एक समूह।

कंप्यूटर प्रोग्राम केवल ऐसी चीजें नहीं हैं जो एल्गोरिदम को निष्पादित करते हैं, वे भी हमारे द्वारा मनुष्यों द्वारा निष्पादित और कार्यान्वित किए जाते हैं।

उदाहरण के लिए, क्या आपने एल्गोरिथ्म के बारे में सोचा है जो निम्नलिखित कार्यों को निष्पादित करता है?

  • अपने दाँतों को ब्रश करें
  • नहाना
  • रसोइया
  • घर से काम करने के लिए ड्राइव

हमारे दिन-प्रतिदिन में, हम ऊपर उल्लिखित कार्यों में से कम से कम एक को पूरा करने के लिए कई चरणों को निष्पादित करते हैं। आइए उदाहरण के रूप में घर से काम करने के लिए कार्य ड्राइविंग का उपयोग करें। मेरे द्वारा उठाए गए कदम मूल रूप से इस प्रकार हैं:

  1. मेरी गाड़ी में बैठ जाओ
  2. उन्हें सवारी देने के लिए एक दोस्त के घर पर ड्राइव करें
  3. जहां मैं काम करता हूं, उस कार्यालय में ड्राइव करें
  4. पार्किंग गैरेज में मेरी कार पार्क करें

यह चरणों का सेट है (एल्गोरिथ्म) मुझे इस कार्य को पूरा करने के लिए प्रदर्शन करने की आवश्यकता है।

अब, उसी कार्य को पूरा करने के लिए आवश्यक कदमों के बारे में सोचें। यह संभावना है कि वे खदान से कुछ अलग हैं। हमारे एल्गोरिदम अलग हो सकते हैं, लेकिन हमारा उद्देश्य एक ही है।

कंप्यूटर प्रोग्राम बहुत अलग नहीं हैं: विभिन्न प्रकार के एल्गोरिदम हैं जिनका उपयोग कार्यों की एक श्रृंखला को करने के लिए किया जा सकता है। अक्सर, हम खुद से चिंता नहीं करते हैं कि वे क्या हैं, हम बस उनका उपयोग करते हैं (खुद शामिल हैं)।

उदाहरण के लिए, वेज़ और गूगल मैप्स द्वारा उपयोग किए जाने वाले एल्गोरिदम को क्या करना चाहिए, जो दो स्थानों के बीच सबसे अच्छे मार्ग की गणना करता है, कैसा दिखता है? नेटफ्लिक्स के एल्गोरिदम के बारे में क्या आपने जो देखा है उसके आधार पर फिल्में और श्रृंखला का सुझाव देता है?

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

एल्गोरिथ्म जटिलता क्या है?

कंप्यूटर विज्ञान में, एल्गोरिथ्म जटिलता से तात्पर्य है कि किसी एल्गोरिथ्म को किसी कार्य को निष्पादित करने में कितना समय और स्थान लगता है, उसके इनपुट के आकार के अनुसार।

आमतौर पर, एल्गोरिदम का मूल्यांकन उनके समय और स्थान दोनों की खपत के आधार पर किया जाता है, लेकिन मैं केवल इस पोस्ट में समय जटिलता को संबोधित करने जा रहा हूं।

समय जटिलता का विश्लेषण हमें यह निर्धारित करने की अनुमति देता है कि एक एल्गोरिथ्म अपने इनपुट तत्वों में वृद्धि को कैसे व्यवहार करेगा। हम उस समय का अंदाजा लगा सकते हैं, जिसमें 10, 100 या 1000 तत्वों को संसाधित करने में समय लगेगा।

और यह विश्लेषण क्यों महत्वपूर्ण है?

  • यह निर्धारित करने के लिए कि कौन सा एल्गोरिथ्म सबसे कुशल है;
  • अधिक कुशल एल्गोरिदम विकसित करने में सक्षम होने के लिए;
  • यह विश्लेषण करने में सक्षम होने के लिए कि क्या एल्गोरिथ्म का पुस्तकालय, या यहां तक ​​कि यह वास्तविक भाषा है, कुशल हैं।

संक्षेप में, दक्षता बिंदु है!

समय जटिलता

किसी गतिविधि के समापन में समय लगता है।

हम आवृत्ति गणना पद्धति के साथ समय का विश्लेषण करना शुरू कर सकते हैं, जो मूल रूप से एक मशीन निर्देश निष्पादित होने की संख्या की गणना करता है। प्रत्येक चरण (निर्देश) को एक समय इकाई दी गई है, जिसकी शुरुआत 1 से है।

एल्गोरिथ्म द्वारा उपभोग किए जाने वाले समय को funcion f (n) द्वारा व्यक्त किया जाता है, जहां n डेटा आकार का प्रतिनिधित्व करता है।

विश्लेषण का परिणाम निम्नानुसार व्यक्त किया जाता है:

((वह कार्य जो समय को व्यक्त करता है]) = [[समय इकाइयों का योग]

अब आइए वास्तविकता को समझने के लिए कुछ एल्गोरिदम का विश्लेषण करें।

पहला फ़ंक्शन दो पूर्ण संख्याओं को जोड़ता है:

हम देख सकते हैं कि, कार्य के लिए, कार्यान्वित एल्गोरिथ्म केवल एक ही चरण को निष्पादित करता है: दो संख्याओं का योग। चूंकि हम प्रत्येक चरण के लिए एक मान रखते हैं, इसलिए परिणाम f (n) = 1 है।

आइए अगले उदाहरण को देखें, जो एक एल्गोरिथ्म है जो एक पूर्णांक को दूसरे पूर्णांक से विभाजित करता है:

सारांश के समान एक गणितीय ऑपरेशन होने के बावजूद, एल्गोरिथ्म में अधिक चरण हैं क्योंकि यह जांचने की आवश्यकता है कि क्या विभाजक 0 है; यदि यह मामला है, तो विभाजन का एहसास नहीं होगा। चूंकि हमारे पास कुल चार चरण हैं, और इनमें से प्रत्येक को 1 का मान दिया गया है, परिणाम f (n) = 4 है।

अगला एल्गोरिदम पूर्णांक की सूची के सभी तत्वों को सम्‍मिलित करता है:

इस एल्गोरिथ्म में, चरणों में से एक में शामिल है, पुनरावृत्ति के लिए एक निर्देश; इसका मतलब यह है कि इसके लिए कोड को कई बार निष्पादित किया जाएगा। चूंकि निष्पादन की संख्या डेटा के आकार पर निर्भर करती है, इसलिए हम समय इकाई के रूप में n के मूल्य को विशेषता देते हैं। परिणाम f (n) = 2n + 3 है।

अगला एल्गोरिथ्म एक सूची का योग दूसरी सूची के योग के साथ जोड़ता है।

परिणामस्वरूप हमारे पास f (n) = 2n 2 + 2n + 3 है।

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

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

उदाहरण के लिए, तीसरे एल्गोरिथम के योग का मुख्य शब्द क्या है?

f (n) = 2n + 3

इस मामले में, 2 * n में प्रमुख शब्द, और मैं समझाऊंगा कि क्यों!

किसी भी स्थिति में जहां n 1 (n> 1) से अधिक है, उत्पाद (गुणन का परिणाम) पहले से ही राशि के दूसरे शब्द से अधिक होगा।

कुछ का परीक्षण करें: 1 से अधिक किसी भी पूर्णांक के साथ n को प्रतिस्थापित करें, और गुणा करें।

पिछले एल्गोरिदम के योग के प्रमुख शब्द के बारे में क्या?

f (n) = 2n² + 2n + 3

इस मामले में, प्रमुख शब्द 2 * n because है, क्योंकि जब n> 1, उत्पाद हमेशा योग के दूसरे और तीसरे शब्दों से अधिक होगा। आगे बढ़ो, यह परीक्षण!

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

यह वह जगह है जहां ऑर्डर ऑफ कॉम्प्लेक्सिटी चलन में आती है, जिसे नोटेशन-ओ या बिग-ओ के नाम से भी जाना जाता है।

बिग-ओ नोटेशन

एक एल्गोरिथ्म को वर्गीकृत करने के लिए उपयोग किया जाता है, जो कि संसाधित तत्वों की संख्या बढ़ने के साथ संचालन की विकास दर पर विचार करता है।

बिग-ओ नोटेशन एक फ़ंक्शन को भी परिभाषित करता है जो एक एल्गोरिथ्म की समय जटिलता को व्यक्त करता है। यह अंत करने के लिए, n अक्षर O के फ़ंक्शन के रूप में उपयोग किया जाता है।

सबसे आम वर्ग हैं:

  • ओ (1) - लगातार, तत्वों की संख्या बढ़ने पर संचालन की संख्या में वृद्धि नहीं होती है
  • ओ (लॉग एन) - लॉगरिदमिक, संचालन की संख्या तत्वों की संख्या से कम है
  • ओ (एन) - रैखिक, तत्वों की संख्या के साथ संचालन की संख्या आनुपातिक रूप से बढ़ जाती है
  • O (n operations) द्विघात, संचालन की संख्या तत्वों की संख्या से अधिक होगी
  • O (2 ^ n) - एक्सपोनेंशियल, तत्वों की संख्या की तुलना में संचालन की संख्या तेजी से बढ़ती है
  • ओ (एन!) - फैक्टरियल, बहुत कम तत्वों के लिए भी, संचालन की संख्या बहुत तेजी से बढ़ती है

नीचे, हमारे पास एक ग्राफिक है जो तत्वों की संचालन x मात्रा की वृद्धि दर दिखाता है:

ग्राफिक को इस प्रकार वर्गीकृत किया गया है:

  • रेड जोन भयानक है, इससे बचें!
  • ऑरेंज ज़ोन ख़राब है, इससे भी बचें!
  • पीला क्षेत्र उचित है, उचित है!
  • लाइट-ग्रीन ज़ोन अच्छा है, अच्छा है!
  • डार्क-ग्रीन ज़ोन उत्कृष्ट है, बधाई!

अब, हम पहले बताए गए एल्गोरिदम को वर्गीकृत करने के लिए बिग-ओ नोटेशन का उपयोग करने जा रहे हैं, हमेशा हमारा मार्गदर्शन करने के लिए अपने प्रमुख शब्द का उपयोग कर रहे हैं।

पहले एल्गोरिथ्म का परिणाम f (n) = 1 था; अर्थ है कि, तत्वों में वृद्धि से स्वतंत्र, एल्गोरिथ्म केवल एक ऑपरेशन को निष्पादित करता है। इस प्रकार, हम एल्गोरिथ्म को कॉन्स्टेंट - ओ (1) के रूप में वर्गीकृत कर सकते हैं।

दूसरा एल्गोरिथ्म परिणामस्वरूप च (n) = 4; अर्थ है कि, तत्वों में वृद्धि से स्वतंत्र, एल्गोरिथ्म चार संचालन को निष्पादित करेगा। इस प्रकार, हम इस एल्गोरिथ्म को कॉन्स्टेंट - ओ (1) के रूप में भी वर्गीकृत कर सकते हैं।

तीसरे एल्गोरिथ्म का परिणाम f (n) = 2n + 3 था; इसका मतलब है कि संचालन की संख्या तत्वों की संख्या के साथ आनुपातिक रूप से बढ़ेगी, यह देखने के लिए कि इस फ़ंक्शन में चर के रूप में एन कैसे कार्य करता है। इस प्रकार, हम इस एल्गोरिथ्म को रैखिक - O (n) के रूप में परिभाषित कर सकते हैं।

अंतिम एल्गोरिथ्म के परिणामस्वरूप f (n) = 2n 2 + 2n + 3 का परिणाम हुआ, जिसका अर्थ है कि संचालन की संख्या तत्वों की संख्या से अधिक बढ़ जाएगी। इस मामले में, n भी एक चर के रूप में कार्य करता है, लेकिन इसे दूसरी शक्ति (चौकोर) तक बढ़ाया जाता है। इस प्रकार, हम इस एल्गोरिथ्म को द्विघात - O (n।) के रूप में परिभाषित कर सकते हैं।

नीचे दी गई तालिका संचालन की संख्या में वृद्धि को दर्शाती है क्योंकि यह तत्वों की संख्या के विकास से संबंधित है।

ध्यान दें कि एक घातांक एल्गोरिथ्म में, 16 तत्वों के परिणामस्वरूप कम से कम 65,5536 ऑपरेशन होंगे। बहुत परेशान, है ना?

सामान्य तौर पर, विश्लेषण प्रक्रिया वही है जो हम कर रहे हैं: चरणों की संख्या की गिनती और प्रमुख शब्द की पहचान करना।

कुछ रुझान जो हम देख सकते हैं:

  • एल्गोरिथ्म जिसमें दोहराव लूप नहीं होता है, वह लगातार होता है - O (1)
  • एल्गोरिथ्म जिसमें पुनरावृत्ति लूप है, जब तक वे नेस्टेड नहीं होते हैं, रैखिक होते हैं - ओ (एन)
  • एल्गोरिथ्म जिसमें दो नेस्टेड दोहराव वाले छोर हैं वे द्विघात होते हैं - O (n that)
  • किसी सरणी के सूचकांक तक सीधी पहुंच आमतौर पर O (1) (स्थिर) होती है
  • सूची विस्तार विधियाँ, औसतन, O (n) हैं। उदाहरण के लिए: कोई भी, सम और फ़िल्टर।
  • बबल सॉर्ट, इंसर्शन सॉर्ट और सिलेक्शन सॉर्ट जैसे एल्गोरिदम को आमतौर पर O (n।) किया जाता है।

एल्गोरिदम को वर्गीकृत करने का तरीका जानने से हमें एल्गोरिथ्म की दक्षता या अक्षमता का न्याय करने की क्षमता मिलती है। बेशक, हम इसके सटीक चलने का समय सेकंड, मिनट या घंटों में नहीं माप सकते। ऐसा करने के लिए, इसे तदनुसार निष्पादित, मापा और बदल दिया जाना चाहिए। कल्पना कीजिए कि ऐसा करने के लिए एल्गोरिदम जो घंटों, या दिन भी लेते हैं, चलाने के लिए? कोई मौका नहीं!

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

मैंने अतिरिक्त पठन सामग्री के रूप में कुछ संदर्भ नीचे छोड़ दिए हैं!

संदर्भ:

विडोस 1 से 1.7

प्रौद्योगिकी के माध्यम से ऋण बाजार में नवीनता लाना चाहते हैं? हम हमेशा हमारे चालक दल में शामिल होने के लिए नए लोगों की तलाश कर रहे हैं!

यहाँ हमारे उद्घाटन की जाँच करें।