Algorithm

Introduction:-

किसी समस्या को हल करने के लिए Step by Step(चरण दर चरण) लिखे गए क्रम को Algorithm (एल्गोरिदम) कहा जाता है। Algorithm (एल्गोरिदम) में बताए गए विभिन्न चरणों को क्रमानुसार रन करता जाता है, और इसी प्रकार एक Program रन होता है। उदाहरण के लिए अपने किसी Friends को Phone  से कोई massage पहुंचाने का Algorithm (एल्गोरिदम) निम्नानुसार होगा:

1. फोन का रिसीवर उठाएं।
2. डायल टोन हो तो मित्र का नंबर डायल करें।
3. मित्र के फोन उठाने तक प्रतीक्षा करें।
4. मित्र के फोन उठाने पर उसे संदेश सुनाएं
5. रिसीवर वापस फोन पर रख दें।

इसी प्रकार दो संख्याओं को जोड़ने के लिए Algorithm (एल्गोरिदम) निम्नानुसार होगाः

1.  पहली संख्या को A नाम के variable (वेरिएबल) में स्टोर करें।
2.  दूसरी संख्या को B नाम के variable (वेरिएबल ) में स्टोर करें।
3.  दोनों का योग करने के लिए निम्नानुसार फॉर्मूला प्रयोग करें:
1. C = A + B
4.  variable (वेरिएबल ) C में प्राप्त वैल्यू को प्रिंट करा दें।

इस प्रकार यह स्पष्ट होता है कि किसी कार्य को करने के क्रमानुसार तरीके को Algorithm (एल्गोरिदम) कहा जाता है। किसी एक कार्य को करने के कई तरीके हो सकते हैं, ऐसे में Programmer (प्रोग्रामर) के लिए बेहतर होता है कि वह उन विभिन्न तरीकों में से श्रेष्ठ का चुनाव करें। ध्यान दें कि Algorithm (एल्गोरिदम) में प्रयोग में आने वाले सभी variables(वेरिएबल्स) Capital letters(केपिटल लैटर्स) में ही आते हैं।

Algorithmic techniques(एल्गोरिदमकी तकनीकें)

Algorithm (एल्गोरिदम) को तकनीक के आधार पर हम दो भागों में विभाजित कर सकते हैं:

1. Incremental Algorithm (इंक्रीमेंटल एल्गोरिदम)
2. Divide and Conquer Algorithm (डिवाइड एंड कॉन्कर एल्गोरिदम)

Incremental Algorithm

इस तकनीक में किसी समस्या को हल करने के लिए top-down system(टॉप-डाउन प्रणाली) का प्रयोग किया जाता है। इसमें अलग-अलग Elements (एलीमेंट्स) को Solve करते हुए अगले छोटे step की तरफ बढ़ा जाता है।
इसमें एक ही Algorithm (एल्गोरिदम) में पूरा हल लिखा जाता है। छोटी Algorithm (एल्गोरिदम) के लिए तो यह तरीका उपयुक्त है किन्तु बड़ी problems को solve करने के लिए यह तकनीक प्रयोग में नहीं लेनी चाहिए। यह तकनीक Modular programming (मॉड्यूलर प्रोग्रामिंग) के विपरीत है।

Divide and Conquer Algorithm 

इस तकनीक में Bottom-up system(बॉटम-अप प्रणाली) प्रयोग में ली जाती है। Bottom-up system(बॉटम-अप प्रणाली) में पहले problems के छोटे-छोटे टुकड़ों के लिए Algorithm (एल्गोरिदम) बना ली जाती है, तथा बाद में उन सभी को marge (मर्ज) कर दिया जाता है।

यह system Modular system का समर्थन करती है। Modular system में सबसे पहले समस्या को छोटे-छोटे हिस्सों में तोड़ दिया जाता है। जब समस्या स्वयं छोटे-छोटे टुकडों में divided हो जाती है तो प्रत्येक टुकड़े के लिए Algorithm (एल्गोरिदम) लिखना काफी आसान कार्य हो जाता है।

इस तकनीक में तीन कार्य किए जाते हैं:

1.  Divide:-  इस चरण में समस्या को अलग-अलग भागों में तोड़ दिया जाता है।
2.  Conquer:-  इस चरण में छोटे टुकड़े को आसानी से हल कर लिया जाता है।
3.  Combine:- इस चरण में हल किए हुए सभी टुकड़ों को जोड़कर संपूर्ण हल तैयार किया जाता है।

Need Of algorithm (एल्गोरिद्म की आवश्यकता)

किसी भी एल्गोरिद्म को लिखते समय यह देख लेना चाहिए कि वह निम्नांकित विशेषताओं से युक्त हो:

1. Finiteness:

प्रत्येक Algorithm (एल्गोरिदम) कुछ निश्चित Steps के बाद End हो जानी चाहिए।

2. Definiteness:-

Algorithm (एल्गोरिदम) में शामिल प्रत्येक step का अर्थ साफ होना चाहिए। अन्य शब्दों में लिखे गए steps के एक से अधिक अर्थ नहीं निकलने चाहिए।

3. input:-

एक Algorithm (एल्गोरिदम) में zero (0) या zero(0) से अधिक input दिए जा सकते हैं।

4. Output:-

Algorithm (एल्गोरिदम) द्वारा कम से कम एक Output ज़रूर दिया जाना चाहिए।

5. Effective:-

Algorithm (एल्गोरिदम) में दिए गए निर्देश ऐसे हो जिनसे कोई परिणाम निकलता हो। व्यर्थ के निर्देश Algorithm (एल्गोरिदम) की significance(सार्थकता) को विपरीत रूप से प्रभावित करते हैं।

Complexity

किसी समस्या को solve करने के लिए Step by Step(चरण दर चरण)   लिखे गए क्रम को Algorithm (एल्गोरिदम) कहा जाता है। किसी समस्या को solve करने के लिए एक से अधिक Algorithm (एल्गोरिदम) हो सकती हैं। ऐसे में कौनसी Algorithm (एल्गोरिदम) का चुनाव किया जाए यह उस Algorithm (एल्गोरिदम) की Complexity (जटिलता) पर निर्भर करता है।

Complexity (जटिलता) की गणना करने के लिए Algorithm (एल्गोरिदम) में लगने वाले time एवं space की गणना की जाती है। वह Algorithm (एल्गोरिदम) सबसे अच्छी होगी जो अन्य के मुकाबले कम time तथा कम space लेती है। इस प्रकार यह कहा जा सकता है कि वह Algorithm (एल्गोरिदम) का चुनाव करते समय Time-Space Tradeoff  का उपयोग किया जाता है। इसे निम्नानुसार दो अलग-अलग भागों में अध्ययन किया जा सकता है:

1. Time Complexity:-

Time Complexity (समय की जटिलता) Algorithm (एल्गोरिदम) के रन होने में लगने वाले time को इंगित करती है। सरल शब्दों में यह कहा जा सकता है कि Time Complexity (समय की जटिलता) के माध्यम से किसी Program द्वारा लिए जाने वाले Time की Calculation की जा सकती है।

Example:- 

माना हमें Railway Reservation (रेलवे रिज़र्वेशन) करवाना है। Reservation (रिज़र्वेशन)  Counter (काउंटर) पर Data इनपुट करने के कुछ सैकंड्स बाद ही टिकट प्रिंट हो जाना चाहिए, अन्यथा टिकट विंडो पर लगी line लंबी होती जाएगी। हम यह कह सकते हैं कि टिकट प्रिंट करने के लिए लगने वाला समय काफी कम होना चाहिए तभी टिकट प्रिंट करने की Algorithm (एल्गोरिदम) की सफलता होगी।

दूसरी तरफ यदि कोई Bank साल में एक बार Income Tax की गणना करती है तो उसमें यदि कुछ सैकंड अधिक लग जाएंगे तो कोई खास फर्क नहीं पड़ेगा। ऐसी स्थिति में time complexity पर तुलनात्मक रूप से अधिक ध्यान देने की आवश्यकता नहीं होगी। उपरोक्त उदाहरण यह बताते हैं कि किसी Algorithm (एल्गोरिदम) में लगने वाले समय की गणना करना एक महत्वपूर्ण कार्य है।

2- Space Complexity

Space Complexity (स्पेस की जटिलता) यह बताती है कि किसी Algorithm (एल्गोरिदम) के पूरा होने में कितनी Space (Memory) की आवश्यकता होगी। किसी समस्या को हल करने के लिए उपलब्ध अलग-अलग Algorithm (एल्गोरिदम) की Memory आवश्यकता भी अलग-अलग हो सकती है।

एक बेहतर Algorithm (एल्गोरिदम) वह है जो कम मैमोरी काम में लेते हुए कार्य करे। अधिक मैमोरी तब काम में आती है जबकि हमारे Algorithm (एल्गोरिदम) में कई Variable (वेरिएबल ) हो । Algorithm (एल्गोरिदम) के विभिन्न Step में जब उन Variables (वेरिएबल्स) को प्रयोग में लिया जाएगा तो उनकी वैल्यू को मैमोरी से पढ़ने का अतिरिक्त कार्य Processer (प्रोसेसर) को करना होगा, जो कि Algorithm (एल्गोरिदम) के रन होने के समय को बढ़ाएगा।

यह कहा जा सकता है कि बेहतर Algorithm (एल्गोरिदम) वह है जो कम से कम memory transaction (मैमोरी ट्रांजेक्शन) करे और यह तभी संभव है जबकि कम Variables (वेरिएबल्स) का प्रयोग किया गया हो। दूसरी तरफ जैसे जैसे Algorithm (एल्गोरिदम) में Input की मात्रा बढ़ती है, वैसे वैसे ही मैमोरी की आवश्यकता भी बढ़ती जाती है। ऐसे में कम मैमोरी का प्रयोग एक चुनौती बन जाता है।

किसी भी Algorithm (एल्गोरिदम) का चुनाव करते समय हमें अलग-अलग Input की मात्रा का उपयोग करते हुए Time और Space की गणना करनी चाहिए। वह Algorithm (एल्गोरिदम) बेहतर मानी जाएगी जो Input की संख्या बढ़ाने पर भी Algorithm (एल्गोरिदम) की complexity को उसी अनुपात में नहीं बढ़ाती हो।

Time-Space Complexity Tradeoff

जैसा कि हम जानते हैं कि एक Problem को Solve करने के लिए अलग-अलग Algorithm (एल्गोरिदम) हो सकती है, तथा वह Algorithm (एल्गोरिदम) बेहतर होती है जो रन होने पर कम से कम Time तथा Memory प्रयोग में ले। यदि हमारे पास Time की कमी है तो ऐसी Algorithm (एल्गोरिदम) को select करेंगे जिसमें कम Time लगे। वहीं यदि हमारे पास Memory सीमित है तो ऐसी Algorithm (एल्गोरिदम) को select करेंगे जो कम Space प्रयोग में ले।

कई बार ऐसा होता है कि किसी Algorithm (एल्गोरिदम) में इनपुट की मात्रा दो गुना कर देने पर (जैसे 1000 संख्याओं को Sort करने की जगह 2000 संख्याओं को Sort करना करना हो तो Algorithm (एल्गोरिदम) भी दो गुना Time लेती है। वहीं कई बार ऐसा भी होता है कि Number of Input को दो गुना कर देने पर Algorithm (एल्गोरिदम) में लगने वाला Time चार गुना बढ़ जाता है।

Time Complexity ऐसा Function है जो यह बताता है कि यदि किसी Algorithm (एल्गोरिदम) में Input की मात्रा को बढ़ा दिया जाए तो उसमें लगने वाला समय कितना बढ़ेगा। 

This article is contributed by Nirma Kanwar If you like W3 Coding club and would like to contribute, you can also write an article and mail on w3codingclub@gmail.com. See your article appearing on the W3 Coding Club main page.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.