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

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

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

पृष्ठभूमि

चार्ल्स बैबेज के यांत्रिक विश्लेषणात्मक इंजन के संबंध में 1843 में एडा लवलेस द्वारा निष्पादन समय पर जोर देने के साथ दक्षता के महत्व पर जोर दिया गया था:

“लगभग सभी कंप्यूटिंग में, प्रक्रिया को सफलतापूर्वक पूरा करने के लिए कॉन्फ़िगरेशन का एक बड़ा विकल्प संभव है, और गणना करने के उद्देश्य से विभिन्न सम्मेलनों को विकल्प को प्रभावित करना चाहिए। आवश्यक बात यह है कि एक ऐसा कॉन्फ़िगरेशन चुनें जिसके परिणामस्वरूप गणना करने में लगने वाला समय कम से कम हो जाएगा।"

प्रारंभिक इलेक्ट्रॉनिक कंप्यूटर गति और मेमोरी दोनों में बहुत सीमित थे। कुछ मामलों में, यह महसूस किया गया है कि टाइम-मेमोरी ट्रेड-ऑफ है, जिसमें किसी कार्य को उच्च गति प्राप्त करने के लिए या तो बड़ी मात्रा में मेमोरी का उपयोग करना पड़ता है, या धीमी एल्गोरिदम का उपयोग करना पड़ता है जो थोड़ी मात्रा में कार्यशील मेमोरी का उपयोग करता है। इस मामले में, सबसे तेज़ एल्गोरिदम का उपयोग किया गया था जिसके लिए उपलब्ध मेमोरी पर्याप्त थी।

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

"स्थापित इंजीनियरिंग विषयों में, 12% सुधार आसानी से प्राप्त किया जा सकता है और इसे कभी भी निषेधात्मक नहीं माना गया है, और मेरा मानना ​​है कि प्रोग्रामिंग में भी यही सच होना चाहिए।"

समीक्षा

एक एल्गोरिदम को कुशल माना जाता है यदि इसकी संसाधन खपत (या संसाधन लागत) कुछ स्वीकार्य स्तर पर या उससे नीचे है। मोटे तौर पर कहें तो, यहां "स्वीकार्य" का अर्थ है "एल्गोरिदम उपलब्ध कंप्यूटर पर उचित समय तक चलेगा।" क्योंकि 1950 के दशक के बाद से कंप्यूटर की प्रसंस्करण शक्ति और उपलब्ध मेमोरी में उल्लेखनीय वृद्धि हुई है, वर्तमान "स्वीकार्य स्तर" 10 साल पहले भी स्वीकार्य नहीं था।

कंप्यूटर निर्माता समय-समय पर नए मॉडल जारी करते हैं, जो अक्सर अधिक शक्तिशाली होते हैं। सॉफ़्टवेयर की लागत काफी अधिक हो सकती है, इसलिए कुछ मामलों में आपके मौजूदा कंप्यूटर के साथ संगत तेज़ कंप्यूटर खरीदकर बेहतर प्रदर्शन प्राप्त करना आसान और सस्ता है।

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

व्यवहार में, ऐसे अन्य कारक हैं जो एल्गोरिदम की प्रभावशीलता को प्रभावित करते हैं, जैसे आवश्यक सटीकता और/या विश्वसनीयता। जैसा कि नीचे बताया गया है, जिस तरह से एल्गोरिदम लागू किया जाता है उसका वास्तविक प्रदर्शन पर भी महत्वपूर्ण प्रभाव पड़ सकता है, हालांकि कार्यान्वयन के कई पहलू अनुकूलन मुद्दे हैं।

सैद्धांतिक विश्लेषण

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

पद का नाम	नाम	उदाहरण
O(1) (\displaystyle O(1)\,)	स्थायी	यह निर्धारित करना कि कोई संख्या सम है या विषम। एक स्थिर आकार लुकअप तालिका का उपयोग करना। किसी तत्व का चयन करने के लिए उपयुक्त हैश फ़ंक्शन का उपयोग करना।
O (लॉग ⁡ n) (\displaystyle O(\log n)\,)	लघुगणक	द्विपद ढेर पर संचालन के समान, बाइनरी खोज या संतुलित पेड़ का उपयोग करके क्रमबद्ध सरणी में एक तत्व ढूंढना।
O(n) (\displaystyle O(n)\,)	रेखीय	किसी अवर्गीकृत सूची या असंतुलित पेड़ में एक तत्व ढूँढना (सबसे खराब स्थिति)। दो का जोड़ एन-बिट नंबर एंड-टू-एंड कैरी का उपयोग करते हुए।
O (n log ⁡ n) (\displaystyle O(n\log n)\,)	अर्धरेखीय, लघुगणकीय रूप से रैखिक	तेज़ फूरियर ट्रांसफ़ॉर्म, हीपसॉर्ट, क्विकसॉर्ट (सर्वोत्तम और औसत मामला), मर्ज सॉर्ट की गणना करें
O (n 2) (\displaystyle O(n^(2))\,)	वर्ग	दो का गुणा करना एन-एक सरल एल्गोरिदम, बबल सॉर्ट (सबसे खराब स्थिति), शैल सॉर्ट, क्विक सॉर्ट (सबसे खराब स्थिति), चयन सॉर्ट, सम्मिलन सॉर्ट का उपयोग करके अंक संख्याएं
O (c n) , c > 1 (\displaystyle O(c^(n)),\;c>1)	घातीय	डायनेमिक प्रोग्रामिंग का उपयोग करके ट्रैवलिंग सेल्समैन की समस्या का (सटीक) समाधान ढूंढना। विस्तृत खोज का उपयोग करके यह निर्धारित करना कि क्या दो तार्किक कथन समतुल्य हैं

सत्यापन परीक्षण: प्रदर्शन को मापना

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

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

कार्यान्वयन के लिए मुद्दें

कार्यान्वयन संबंधी समस्याएं वास्तविक प्रदर्शन को भी प्रभावित कर सकती हैं। इसमें प्रोग्रामिंग भाषा का चुनाव और एल्गोरिदम को वास्तव में कोडित करने का तरीका, चुनी गई भाषा के लिए अनुवादक का विकल्प या उपयोग किए गए कंपाइलर विकल्प और यहां तक ​​कि उपयोग किए गए ऑपरेटिंग सिस्टम का चयन भी शामिल है। कुछ मामलों में, एक दुभाषिया के रूप में लागू की गई भाषा एक कंपाइलर के रूप में लागू की गई भाषा की तुलना में काफी धीमी हो सकती है।

ऐसे अन्य कारक हैं जो समय या मेमोरी उपयोग को प्रभावित कर सकते हैं जो प्रोग्रामर के नियंत्रण से परे हैं। इसमें डेटा संरेखण शामिल है, का ब्यौरा, कचरा संग्रहण , अनुदेश-स्तरीय समानता और सबरूटीन कॉलिंग।

कुछ प्रोसेसर में वेक्टर ऑपरेशन करने की क्षमता होती है, जो एक ऑपरेशन को कई ऑपरेंड को प्रोसेस करने की अनुमति देती है। प्रोग्रामिंग या संकलन स्तर पर ऐसी सुविधाओं का उपयोग करना आसान हो भी सकता है और नहीं भी। अनुक्रमिक कंप्यूटिंग के लिए डिज़ाइन किए गए एल्गोरिदम को समानांतर कंप्यूटिंग को समायोजित करने के लिए पूर्ण रीडिज़ाइन की आवश्यकता हो सकती है।

प्रोसेसर संगतता के साथ एक और समस्या उत्पन्न हो सकती है, जहां निर्देशों को अलग-अलग तरीके से लागू किया जा सकता है, ताकि कुछ मॉडलों पर निर्देश अन्य मॉडलों पर अपेक्षाकृत धीमे हो सकें। यह अनुकूलन कंपाइलर के लिए एक समस्या हो सकती है।

संसाधन उपयोग मापना

माप आमतौर पर प्रवेश द्वार के आकार के आधार पर व्यक्त किए जाते हैं एन.

दो सबसे महत्वपूर्ण आयाम हैं:

• समय: एल्गोरिदम सीपीयू पर कितना समय लेता है।
• याद: एल्गोरिदम के लिए कितनी कार्यशील मेमोरी (आमतौर पर रैम) की आवश्यकता होती है। इसके दो पहलू हैं: कोड के लिए मेमोरी की मात्रा और उस डेटा के लिए मेमोरी की मात्रा जिस पर कोड संचालित होता है।

बैटरी चालित कंप्यूटरों (जैसे लैपटॉप) या बहुत लंबी/बड़ी गणनाओं (जैसे सुपर कंप्यूटर) के लिए, एक अलग प्रकार का माप रुचिकर होता है:

• प्रत्यक्ष ऊर्जा खपत: कंप्यूटर चलाने के लिए आवश्यक ऊर्जा।
• अप्रत्यक्ष ऊर्जा खपत: शीतलन, प्रकाश आदि के लिए आवश्यक ऊर्जा।

कुछ मामलों में, अन्य, कम सामान्य मापों की आवश्यकता होती है:

• गियर का आकार: बैंडविड्थ सीमित कारक हो सकता है। स्थानांतरित किए गए डेटा की मात्रा को कम करने के लिए संपीड़न का उपयोग किया जा सकता है। एक चित्र या छवि (जैसे Google लोगो) प्रदर्शित करने से हजारों बाइट्स स्थानांतरित हो सकती हैं (इस मामले में 48K)। इसकी तुलना "Google" शब्द में छह बाइट्स ट्रांसमिट करने से करें।
• बाह्य स्मृति: डिस्क या अन्य बाहरी स्टोरेज डिवाइस पर आवश्यक मेमोरी। इस मेमोरी का उपयोग अस्थायी भंडारण या भविष्य में उपयोग के लिए किया जा सकता है।
• प्रतिक्रिया समय: यह सेटिंग वास्तविक समय के अनुप्रयोगों के लिए विशेष रूप से महत्वपूर्ण है जहां कंप्यूटर को बाहरी घटनाओं पर तुरंत प्रतिक्रिया देनी होती है।
• मालिकाने की कुल कीमत: पैरामीटर तब महत्वपूर्ण होता है जब इसका उद्देश्य एकल एल्गोरिदम निष्पादित करना होता है।

समय

लिखित

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

याद

यह अनुभाग एल्गोरिथम के लिए आवश्यक मुख्य मेमोरी (अक्सर रैम) के उपयोग से संबंधित है। जैसा कि ऊपर दिए गए समय विश्लेषण के साथ होता है, आमतौर पर एक एल्गोरिदम का विश्लेषण उपयोग किया जाता है एल्गोरिथ्म की स्थानिक जटिलताइनपुट आकार के फ़ंक्शन के रूप में आवश्यक रनटाइम मेमोरी का अनुमान लगाने के लिए। परिणाम आमतौर पर बड़े "ओ" के रूप में व्यक्त किया जाता है।

मेमोरी उपयोग के चार पहलू हैं:

• एल्गोरिथम कोड को संग्रहीत करने के लिए आवश्यक मेमोरी की मात्रा।
• इनपुट डेटा के लिए आवश्यक मेमोरी की मात्रा.
• किसी भी आउटपुट के लिए आवश्यक मेमोरी की मात्रा (कुछ एल्गोरिदम, जैसे सॉर्ट्स, अक्सर इनपुट को पुनर्व्यवस्थित करते हैं और आउटपुट के लिए अतिरिक्त मेमोरी की आवश्यकता नहीं होती है)।
• गणना के दौरान कम्प्यूटेशनल प्रक्रिया द्वारा आवश्यक मेमोरी की मात्रा (इसमें नामित चर और सबरूटीन कॉल के लिए आवश्यक कोई भी स्टैक स्पेस शामिल है, जो रिकर्सन का उपयोग करते समय महत्वपूर्ण हो सकता है)।

प्रारंभिक इलेक्ट्रॉनिक कंप्यूटर और घरेलू कंप्यूटर में अपेक्षाकृत कम कार्यशील मेमोरी क्षमता होती थी। इस प्रकार, 1949 में ईडीएसएसी में 1024 17-बिट शब्दों की अधिकतम कार्यशील मेमोरी थी, और 1980 में सिंक्लेयर ZX80 को 1024 बाइट्स की कार्यशील मेमोरी के साथ जारी किया गया था।

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

• कैश (अक्सर स्थिर रैम) - सीपीयू की तुलना में गति पर चलता है
• मुख्य भौतिक मेमोरी (अक्सर डायनेमिक रैम) - सीपीयू की तुलना में थोड़ी धीमी गति से चलती है
• वर्चुअल मेमोरी (अक्सर डिस्क पर) - विशाल मेमोरी का भ्रम देती है, लेकिन रैम की तुलना में हजारों गुना धीमी गति से काम करती है।

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

इलेक्ट्रॉनिक कंप्यूटिंग के शुरुआती दिनों में, यदि कोई एल्गोरिदम और उसका डेटा मुख्य मेमोरी में फिट नहीं होता था, तो इसका उपयोग नहीं किया जा सकता था। इन दिनों, वर्चुअल मेमोरी का उपयोग बड़े पैमाने पर मेमोरी प्रदान करता है, लेकिन प्रदर्शन की कीमत पर। यदि एल्गोरिदम और उसका डेटा कैश में फिट होता है, तो बहुत तेज़ गति प्राप्त की जा सकती है, इसलिए आवश्यक मेमोरी को कम करने से समय को कम करने में मदद मिलती है। एक एल्गोरिदम जो पूरी तरह से कैश में फिट नहीं होता है, लेकिन प्रदान करता है लिंक का स्थान, अपेक्षाकृत तेजी से काम कर सकता है।

प्रभावी एल्गोरिदम के उदाहरण

प्रोग्रामिंग की वर्तमान स्थिति की आलोचना

जितनी तेजी से कंप्यूटर तेज हो रहे हैं, उससे कहीं ज्यादा तेजी से प्रोग्राम धीमे होते जा रहे हैं।

मई कहता है:

व्यापक प्रणालियों में, निर्देश निष्पादन को आधा करने से बैटरी जीवन दोगुना हो सकता है, और बड़ा डेटा बेहतर एल्गोरिदम के लिए अवसर प्रदान करता है: एन एक्स एन से एन एक्स लॉग (एन) तक संचालन की संख्या को कम करने से बड़े एन के लिए एक मजबूत प्रभाव पड़ता है... एन के लिए =30 बिलियन, ये परिवर्तन 50 वर्षों के तकनीकी सुधार के समान हैं।

सर्वोत्तम एल्गोरिथम के लिए प्रतियोगिता

निम्नलिखित प्रतियोगिताएं सर्वोत्तम एल्गोरिदम के विकास में भागीदारी को आमंत्रित करती हैं, जिनके गुणवत्ता मानदंड न्यायाधीशों द्वारा निर्धारित किए जाते हैं:

यह सभी देखें

• अंकगणित कोडिंग एक प्रकार की एन्ट्रापी कोडिंग है परिवर्तनीय कोड लंबाई के साथकुशल डेटा संपीड़न के लिए
• एसोसिएटिव ऐरे एक डेटा संरचना है जिसे उपयोग करने पर अधिक कुशल बनाया जा सकता है पेड़ पेट्रीसियाया जूडी सरणियाँ
• प्रदर्शन परीक्षण - कुछ मामलों में तुलनात्मक निष्पादन समय मापने की एक विधि
• सबसे अच्छा, सबसे खराब और औसत मामला- तीन परिदृश्यों के लिए निष्पादन समय का अनुमान लगाने के लिए परंपराएँ
• क्रमबद्ध सूची खोजने के लिए बाइनरी खोज एक सरल और प्रभावी तकनीक है
• शाखा तालिका

व्याख्यान के लक्ष्य और उद्देश्य: एल्गोरिदम और डेटा संरचनाओं की जटिलता और दक्षता का विश्लेषण करने के तरीकों का परिचय

मुख्य मुद्दे: एल्गोरिदम की प्रभावशीलता का प्रयोगात्मक और विश्लेषणात्मक विश्लेषण।

एन. विर्थ का क्लासिक कथन "एक अच्छा प्रोग्राम एक सुविचारित एल्गोरिदम और प्रभावी डेटा संरचनाओं की एकता है।"

एल्गोरिथम विश्लेषण
"एल्गोरिदम और डेटा संरचनाओं" की अवधारणाएं कंप्यूटर प्रौद्योगिकी के क्षेत्र में केंद्रीय हैं, लेकिन कुछ डेटा संरचनाओं और एल्गोरिदम को "उच्च-गुणवत्ता और कुशल" कहने के लिए, उनका विश्लेषण करने के लिए सटीक तकनीकों का उपयोग किया जाना चाहिए। एक प्राकृतिक गुणवत्ता मानदंड के रूप में, सबसे पहले, निष्पादन समय को उजागर करना स्वाभाविक है। खर्च की गई मेमोरी और डिस्क स्थान संसाधनों की मात्रा, डेटा एक्सेस की गति (डेटा संरचना की दक्षता) भी महत्वपूर्ण है। निर्णयों की विश्वसनीयता एवं विश्वसनीयता, उनकी स्थिरता पर भी ध्यान देना चाहिए।

एल्गोरिथम को किसी विशिष्ट कार्यान्वयन से नहीं जोड़ा जाना चाहिए। उपयोग किए जाने वाले प्रोग्रामिंग टूल की विविधता के कारण, कार्यान्वयन में भिन्न एल्गोरिदम ऐसे परिणाम उत्पन्न कर सकते हैं जो दक्षता में भिन्न होते हैं।

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

हालाँकि, यह याद रखना चाहिए कि समय का अनुमान लगाने की यह विधि सटीक नहीं है; सबसे पहले, यह समझा जाना चाहिए कि आधुनिक ऑपरेटिंग सिस्टम में कई कार्यों को समानांतर में निष्पादित किया जा सकता है और एक परीक्षण मामले के निष्पादन को अन्य प्रकारों के साथ जोड़ा जा सकता है। गतिविधि का. इसके अलावा, यह समझा जाना चाहिए कि बार-बार परीक्षण करने से ही स्थिर निर्भरता प्राप्त की जा सकती है, अन्यथा, प्रारंभिक डेटा की बारीकियों और अन्य कारकों के आधार पर यादृच्छिक कारकों के काम के अंतिम परिणाम पर प्रभाव के कारण, निष्पादन एल्गोरिदम का समय भी एक यादृच्छिक चर होगा। अनुसंधान करते समय, एल्गोरिदम को प्रारंभिक डेटा के एक अलग सेट के साथ चलाना आवश्यक होता है; आमतौर पर डेटा स्वयं यादृच्छिक रूप से उत्पन्न होता है, इसलिए डेटा के विभिन्न सेटों के कारण, खर्च किया गया समय भी भिन्न होगा।

एक बार अनुमानों का एक सेट प्राप्त हो जाने पर, एक ग्राफ़ बनाया और अनुमानित किया जा सकता है।

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

सामान्य तौर पर, हम कह सकते हैं कि स्रोत डेटा का आकार बढ़ने पर एल्गोरिदम या डेटा संरचना विधि का निष्पादन समय बढ़ता है, हालांकि यह डेटा के प्रकार पर भी निर्भर करता है, भले ही आकार बराबर हो। इसके अलावा, निष्पादन समय हार्डवेयर (प्रोसेसर, घड़ी आवृत्ति, मेमोरी आकार, डिस्क स्थान, आदि) और सॉफ्टवेयर (ऑपरेटिंग वातावरण, प्रोग्रामिंग भाषा, कंपाइलर, दुभाषिया, आदि) पर निर्भर करता है जिसके साथ कार्यान्वयन, संकलन किया जाता है और एल्गोरिथ्म का निष्पादन. उदाहरण के लिए, अन्य सभी चीजें समान होने पर, अधिक शक्तिशाली कंप्यूटर का उपयोग करते समय या मशीन कोड में प्रोग्राम के रूप में एल्गोरिदम लिखते समय स्रोत डेटा की एक निश्चित मात्रा के लिए एल्गोरिदम का निष्पादन समय वर्चुअल मशीन द्वारा इसके निष्पादन की तुलना में कम होगा। इसे बाइटकोड में व्याख्या करना।

निष्कर्ष यह है कि एल्गोरिदम का अनुभवजन्य विश्लेषण करना वास्तव में विश्वसनीय नहीं है। मुख्य नुकसानों को निम्नलिखित तीन बिंदुओं तक कम किया जा सकता है:

1) प्रयोग केवल प्रारंभिक डेटा के सीमित सेट का उपयोग करके ही किए जा सकते हैं; दूसरे सेट का उपयोग करके प्राप्त परिणामों पर ध्यान नहीं दिया जाता है।

2) दो एल्गोरिदम की प्रभावशीलता की तुलना करने के लिए, यह आवश्यक है कि उनके निष्पादन समय को निर्धारित करने के लिए प्रयोग एक ही हार्डवेयर और सॉफ्टवेयर पर किए जाएं;
3) एल्गोरिथम के निष्पादन समय का प्रयोगात्मक रूप से अध्ययन करने के लिए, इसके कार्यान्वयन और निष्पादन को अंजाम देना आवश्यक है।

इस प्रकार, हमें एल्गोरिदम का विश्लेषण करने के लिए सामान्य विश्लेषण विधियों का उपयोग करने की आवश्यकता आती है, जो अनुमति देता है:

1) विभिन्न प्रकार के इनपुट डेटा को ध्यान में रखता है;

2) आपको हार्डवेयर और सॉफ्टवेयर की परवाह किए बिना किन्हीं दो एल्गोरिदम की सापेक्ष प्रभावशीलता का मूल्यांकन करने की अनुमति देता है;

3) एल्गोरिदम के विवरण के अनुसार इसके प्रत्यक्ष कार्यान्वयन या प्रयोगों के बिना किया जा सकता है।

सामान्य विश्लेषण का सार यह है कि फ़ंक्शन f=f(n1, .., nm) को एक निश्चित एल्गोरिदम को सौंपा गया है। अपने सरलतम रूप में, यह एक चर n1 का एक फ़ंक्शन है - इनपुट डेटा की मात्रा। हालाँकि, अन्य चर भी हो सकते हैं - उदाहरण के लिए, गणना की सटीकता या इसकी विश्वसनीयता। इसलिए, यह निर्धारित करने के लिए कि बड़ी संख्याओं (बाइनरी प्रतिनिधित्व की लंबाई 200 बिट्स से अधिक है) के मामले में एक निश्चित संख्या अभाज्य है या नहीं, एक संभाव्य विधि का उपयोग किया जाता है, जिसकी विश्वसनीयता भिन्न हो सकती है। सबसे प्रसिद्ध फ़ंक्शन रैखिक, शक्ति और लघुगणक हैं। इसलिए, आपको उनके साथ काम करने की बुनियादी बातें याद रखने के लिए समय निकालना चाहिए।

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

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

कभी-कभी कथन सामान्यीकृत रूप में लिखे जाते हैं: “सेट एस में संपत्ति वी के साथ एक तत्व एक्स होता है। इस कथन को सिद्ध करने के लिए, एक उदाहरण देना पर्याप्त है कि x, s से "संबंधित" है, जिसमें यह गुण है। ऐसे सामान्यीकृत रूप में, एक नियम के रूप में, असंभावित कथन लिखे जाते हैं, उदाहरण के लिए: "सेट एस के प्रत्येक तत्व x में संपत्ति पी है।" इस कथन की भ्रांति को साबित करने के लिए, केवल एक उदाहरण देना पर्याप्त है: x, s से "संबंधित" है, जिसमें संपत्ति P नहीं है। इस मामले में, तत्व x एक प्रति-उदाहरण के रूप में कार्य करेगा।

उदाहरण:यह कहा गया है कि फॉर्म 2^n - 1 की कोई भी संख्या अभाज्य है यदि n 1 से बड़ा पूर्णांक है। कथन गलत है।

सबूत:किसी को ग़लत साबित करने के लिए, आपको एक प्रति-उदाहरण ढूँढ़ना होगा।

यह एक प्रति-उदाहरण है: 2^4 - 1 = 15, 15= 3 * 5।

एक और तरीका है, जो विरोधाभास द्वारा प्रमाण (निषेध का उपयोग करके) पर आधारित है। इस मामले में मुख्य विधियाँ विरोधाभास और विरोधाभास हैं। कंट्रास्ट विधियों का उपयोग मिररिंग के समान है: यह साबित करने के लिए कि "यदि x सत्य है, तो y सत्य है," हम इसके विपरीत दावा करेंगे, "यदि y गलत है, तो x गलत है।" तार्किक दृष्टिकोण से, ये कथन समान हैं, लेकिन दूसरी अभिव्यक्ति, जो पहले का सह-स्थान है, अधिक सुविधाजनक है।

उदाहरण:यदि a*b एक विषम संख्या है, तो a विषम है या b विषम है।

सबूत:इस कथन को सिद्ध करने के लिए, विरोधाभास पर विचार करें: “यदि a एक सम संख्या है और b विषम है, तो a*b सम है। मान लीजिए कि किसी पूर्णांक x के लिए a = 2*x है। तब a*b = 2*i*b, और इसलिए गुणनफल a*b सम है।

विरोधाभास द्वारा प्रमाण के तरीकों का उपयोग करते समय तर्क का उपयोग करना उपयोगी होता है।

ए या बी = को निष्पादित करने के लिए ए या बी की आवश्यकता होती है, या एक ही समय में ए और बी दोनों की आवश्यकता होती है।
. ए और बी = को ए और बी को एक साथ निष्पादित करने की आवश्यकता है।
. a xor b = को a के निष्पादन की आवश्यकता है, लेकिन b की नहीं, या b की, लेकिन a की नहीं।

किसी कथन q को सत्य साबित करने के लिए विरोधाभास विधि का उपयोग करते समय, पहले यह मान लिया जाता है कि q गलत है और फिर दिखाता है कि ऐसी धारणा विरोधाभास की ओर ले जाती है (उदाहरण के लिए, 2 * 2<>4). इस तरह के विरोधाभास पर आकर, हम यह तर्क दे सकते हैं कि ऐसी स्थिति मौजूद नहीं है जिसमें q गलत है, और, इसलिए, q सच है।

ज्यादातर मामलों में, प्रोग्राम निष्पादन समय या स्थान उपयोग के बारे में बयान पूर्णांक पैरामीटर n (समस्या के "आकार" का प्रतिनिधित्व) का उपयोग करते हैं। फिर जब हम एक कथन x(n) बनाते हैं, तो मानों के एक सेट के लिए n ऐसे कथन समतुल्य होते हैं। चूँकि यह कथन संख्याओं के "अनंत" सेट पर लागू होता है, इसलिए संपूर्ण प्रत्यक्ष प्रमाण प्रदान करना असंभव है। ऐसी स्थितियों में, प्रेरण विधियों का उपयोग किया जाता है। प्रेरण की विधि तथ्य पर आधारित है; किसी भी n > 1 के लिए। क्रियाओं का एक सीमित क्रम होता है जो सत्य मानी जाने वाली किसी चीज़ से शुरू होता है और अंततः इस प्रमाण की ओर ले जाता है कि q(n) सत्य है। इस प्रकार, प्रेरण द्वारा एक प्रमाण इस कथन से शुरू होता है कि q(n) n=1,2,3, आदि के लिए सत्य है। कुछ स्थिरांक k तक। आगे हम सिद्ध करते हैं कि प्रेरण q(n+1), q(n+2) का अगला "चरण" n > k के लिए भी सत्य है।

एल्गोरिदम का विश्लेषण करते समय, संचालन की संख्या और उनके निष्पादन समय की गणना करते समय, किसी को "छोटे विवरण" को ध्यान में नहीं रखना चाहिए और स्थिरांक की उपेक्षा की जानी चाहिए; व्यवहार में, एक बड़े फ़ंक्शन की अवधारणा का उपयोग किया जाता है के बारे में. मान लीजिए कि दो फलन f(n) और g(n) हैं, तो यह माना जाता है कि f(n)<= O(g(n)) , т.е. функция О ограничивает сверху значения функции f, начиная с n=n0.

उदाहरण के लिए, किसी सरणी में शून्य के बराबर तत्वों की संख्या की गणना करने के लिए एल्गोरिदम को O(n) द्वारा वर्णित किया गया है, जहां n तत्वों की संख्या है।

1) 20n3+7.2n2-21.78n + 5 को O(n3) के रूप में वर्णित किया गया है

2)xn-2 + a(0) को O(xn) के रूप में वर्णित किया गया है।

2) 3*लॉग(एन) + लॉग(लॉग(एन)) को ओ(लॉग(एन)) के रूप में वर्णित किया गया है।

3) 2100 को O(1) के रूप में वर्णित किया गया है

4) 5/n को O(1/n) के रूप में वर्णित किया गया है।

कृपया ध्यान दें कि फ़ंक्शन ओ(एन) ऊपर से लक्ष्य समय लागत फ़ंक्शन को सीमित करता है, लेकिन आपको हमेशा ऐसे फ़ंक्शन ओ(एन) को चुनने का प्रयास करना चाहिए जिसमें अधिकतम सटीकता हो।

सबसे प्रसिद्ध O आरोही क्रम में कार्य करता है:

एसिम्प्टोटिक विश्लेषण का उपयोग करते समय, सावधान रहें कि जब आप ओ नोटेशन का उपयोग करते हैं, तो आप अक्सर निरंतर कारकों और अतिरिक्त स्थिरांक की उपेक्षा करते हैं। हालाँकि, यदि यह मान काफी बड़ा है, हालाँकि फ़ंक्शन O(1) का रूप फ़ंक्शन O(n) द्वारा वर्णित एल्गोरिदम की तुलना में अधिक बेहतर है, तो यह निश्चित रूप से दूसरा एल्गोरिदम है जो व्यावहारिक अनुप्रयोग प्राप्त करेगा।

फ़ंक्शन f(n) के प्रकार के आधार पर, एल्गोरिदम की जटिलता के निम्नलिखित वर्गों को प्रतिष्ठित किया जाता है।

जटिलता फ़ंक्शन के आधार पर एल्गोरिदम जटिलता वर्ग
देखें f(n)	एल्गोरिदम के वर्ग की विशेषताएं
	अधिकांश कार्यों के लिए अधिकांश निर्देश एक या अधिक बार निष्पादित होते हैं। यदि किसी प्रोग्राम के सभी निर्देशों में यह गुण है, तो प्रोग्राम का निष्पादन समय स्थिर रहता है।
लॉग एन	जब किसी प्रोग्राम का निष्पादन समय लॉगरिदमिक होता है, तो N बढ़ने पर प्रोग्राम धीमा हो जाता है। ऐसे निष्पादन समय आम तौर पर उन प्रोग्रामों से जुड़े होते हैं जो एक बड़ी समस्या को छोटी उप-समस्याओं के समूह में बदल देते हैं, जिससे प्रत्येक चरण पर कुछ स्थिर कारकों द्वारा समस्या का आकार कम हो जाता है। आधार बदलने से लघुगणक के मान में परिवर्तन पर बहुत अधिक प्रभाव नहीं पड़ता है: n
एन	जब किसी प्रोग्राम का निष्पादन समय रैखिक होता है, तो इसका आमतौर पर मतलब होता है कि प्रत्येक इनपुट तत्व कम प्रसंस्करण से गुजरता है।
एन लॉग एन	एन लॉग एन के आनुपातिक रनटाइम तब होता है जब एक एल्गोरिदम किसी समस्या को छोटी उप-समस्याओं में तोड़कर, उन्हें स्वतंत्र रूप से हल करके और फिर समाधानों को संयोजित करके हल करता है।
एन 2	जब किसी एल्गोरिदम का चलने का समय द्विघात होता है, तो यह अपेक्षाकृत छोटी समस्याओं को हल करने में व्यावहारिक उपयोग के लिए उपयोगी होता है। द्विघात निष्पादन समय आम तौर पर एल्गोरिदम में दिखाई देता है जो डेटा आइटम के सभी जोड़े को संसाधित करता है (शायद डबल-नेस्टेड लूप में)।
एन 3	एक समान एल्गोरिदम जो डेटा तत्वों के ट्रिपल को संसाधित करता है (संभवतः ट्रिपल-नेस्टिंग लूप में) में घन निष्पादन समय होता है और व्यावहारिक रूप से केवल छोटी समस्याओं के लिए लागू होता है।
2एन	घातीय रनिंग टाइम वाले केवल कुछ एल्गोरिदम में व्यावहारिक अनुप्रयोग होते हैं, हालांकि किसी समस्या को सीधे हल करने का प्रयास करते समय ऐसे एल्गोरिदम स्वाभाविक रूप से उत्पन्न होते हैं, जैसे कि क्रूर बल।

अनंत पर जटिलता के स्पर्शोन्मुख कार्यों का अध्ययन करने के लिए गणितीय तरीकों के आधार पर, एल्गोरिदम के पांच वर्गों की पहचान की गई है।

1. निरंतर निष्पादन समय के साथ तेज़ एल्गोरिदम का एक वर्ग, उनका जटिलता फ़ंक्शन O(1) है। मध्यवर्ती स्थिति पर जटिलता ओ (लॉग एन) वाले एल्गोरिदम का कब्जा है, जिन्हें भी इस वर्ग में वर्गीकृत किया गया है।

2. तर्कसंगत या बहुपद एल्गोरिदम का एक वर्ग, जिसकी जटिलता फ़ंक्शन इनपुट मापदंडों से बहुपद रूप से निर्धारित होती है। उदाहरण के लिए, O(N), O(N 2, O(N 3)।

3. जटिलता की डिग्री ओ (एन लॉग एन) के साथ उपघातीय एल्गोरिदम का एक वर्ग।

4. जटिलता की डिग्री O(2 N) के साथ घातीय एल्गोरिदम का वर्ग।

5. ओवरएक्सपोनेंशियल एल्गोरिदम का वर्ग। तथ्यात्मक जटिलता वाले एल्गोरिदम मौजूद हैं, लेकिन उनका आम तौर पर कोई व्यावहारिक अनुप्रयोग नहीं होता है।

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

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

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

• "निम्नलिखित" निर्माण की जटिलता एक दूसरे का अनुसरण करने वाले ब्लॉकों की जटिलता का योग है: f=f 1 +f 2 +...+f n ।
• "ब्रांचिंग" डिज़ाइन की जटिलता स्थिति द्वारा निर्धारित प्रत्येक निर्देश में संक्रमण की संभावना के माध्यम से निर्धारित की जाती है। वहीं, स्थिति की जांच करने में भी एक निश्चित जटिलता होती है। सबसे खराब स्थिति की जटिलता की गणना करने के लिए, सबसे अधिक जटिलता वाले ब्रांचिंग ब्लॉक का चयन किया जा सकता है; सर्वोत्तम स्थिति के लिए, कम जटिलता वाले ब्लॉक का चयन किया जा सकता है। f यदि =f 1 +f तब p तब +f अन्यथा (1-p तब)
• "लूप" निर्माण की जटिलता लूप समाप्ति स्थिति (आमतौर पर क्रम 0(1)) की गणना और लूप बॉडी के संचालन की सबसे बड़ी संभव संख्या द्वारा लूप के पूर्ण पुनरावृत्तियों की संख्या के उत्पाद द्वारा निर्धारित की जाती है। यदि नेस्टेड लूप का उपयोग किया जाता है, तो उनकी जटिलता कई गुना बढ़ जाती है।

इस प्रकार, एल्गोरिदम की जटिलता का अनुमान लगाने के लिए, जटिलता फ़ंक्शन प्राप्त करने के लिए एक सामान्य विधि तैयार की जा सकती है।

1. एल्गोरिथम के अपघटन में एल्गोरिथम में बुनियादी संरचनाओं की पहचान करना और जटिलता का अनुमान लगाना शामिल है। इस मामले में, निम्नलिखित मुख्य एल्गोरिथम संरचनाओं पर विचार किया जाता है।
2. बुनियादी भाषा संचालन के लिए श्रम तीव्रता का लाइन-बाय-लाइन विश्लेषण या तो संचयी विश्लेषण (सभी कार्यों को ध्यान में रखते हुए) या परिचालन विश्लेषण (प्रत्येक ऑपरेशन की जटिलता को ध्यान में रखते हुए) का तात्पर्य है।
3. सर्वोत्तम, औसत और सबसे खराब मामलों के लिए बुनियादी एल्गोरिथम संरचनाओं का विश्लेषण करने की पद्धति के आधार पर जटिलता फ़ंक्शन की व्युत्क्रम संरचना।

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

प्रोग्रामर की लाइब्रेरी

"यदि डिबगिंग त्रुटियों को दूर करने की एक प्रक्रिया है, तो प्रोग्रामिंग उन्हें पेश करने की एक प्रक्रिया होनी चाहिए"

ई. डिज्क्स्ट्रा

1.2. एल्गोरिदम का अध्ययन क्यों करें? एल्गोरिदम की दक्षता

सबसे पहले, कंप्यूटर विज्ञान के विभिन्न क्षेत्रों में किसी भी समस्या को हल करने के लिए एल्गोरिदम महत्वपूर्ण घटक हैं। प्रौद्योगिकी विकास के वर्तमान चरण में एल्गोरिदम एक महत्वपूर्ण भूमिका निभाते हैं। यहां आप ऐसे सामान्य कार्यों को याद कर सकते हैं जैसे:

• अलग-अलग जटिलता के गणितीय समीकरणों को हल करना, आव्यूहों, व्युत्क्रम आव्यूहों का गुणनफल खोजना;
• माल और लोगों के परिवहन के सर्वोत्तम तरीके खोजना;
• विभिन्न नोड्स (निर्माताओं, मशीनों, श्रमिकों, प्रोसेसर, आदि) के बीच संसाधनों को वितरित करने के लिए इष्टतम विकल्प ढूंढना;
• जीनोम में मेल खाने वाले अनुक्रम ढूंढना;
• वैश्विक इंटरनेट पर जानकारी खोजना;
• ई-कॉमर्स में वित्तीय निर्णय लेना;
• ऑडियो और वीडियो जानकारी का प्रसंस्करण और विश्लेषण।

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

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

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

1.3. एल्गोरिदम की दक्षता

आइए मान लें कि कंप्यूटर की गति और उसकी मेमोरी की मात्रा को अनिश्चित काल तक बढ़ाया जा सकता है। क्या तब एल्गोरिदम का अध्ययन करने की आवश्यकता होगी? हां, लेकिन केवल यह प्रदर्शित करने के लिए कि डिकॉउलिंग विधि का चलने का समय सीमित है और यह सही उत्तर देता है। यदि कंप्यूटर असीम रूप से तेज़ होते, तो किसी समस्या को हल करने के लिए एक मनमाना सही तरीका काम करता। बेशक, तब अक्सर वही तरीका चुना जाएगा जिसे लागू करना आसान हो।

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

एक ही समस्या को हल करने के लिए डिज़ाइन किए गए एल्गोरिदम अक्सर दक्षता में बहुत भिन्न हो सकते हैं। ये अंतर विभिन्न हार्डवेयर और सॉफ़्टवेयर के कारण होने वाले अंतर से कहीं अधिक ध्यान देने योग्य हो सकते हैं।

जैसा कि ऊपर बताया गया है, यह अनुभाग छँटाई कार्य पर ध्यान केंद्रित करेगा। पहला एल्गोरिदम जिस पर विचार किया जाएगा, समावेशन सॉर्ट, को काम करने के लिए समय की आवश्यकता होती है, जिसकी मात्रा सी 1 एन 2 के रूप में अनुमानित की जाती है, जहां एन इनपुट डेटा का आकार है (क्रम में सॉर्ट किए जाने वाले तत्वों की संख्या), सी 1 कुछ स्थिरांक है. यह अभिव्यक्ति इंगित करती है कि एल्गोरिदम का चलने का समय स्रोत डेटा की मात्रा पर कैसे निर्भर करता है। समावेशन प्रकार के मामले में, यह निर्भरता द्विघात है। दूसरे एल्गोरिदम, मर्ज सॉर्ट के लिए समय की आवश्यकता होती है, जिसकी मात्रा 2 nLog 2 n अनुमानित की जाती है। आमतौर पर, समावेशन सॉर्ट स्थिरांक मर्ज सॉर्ट स्थिरांक से छोटा होता है, अर्थात, iLog 2 n फ़ंक्शन की तुलना में n बढ़ने पर c12 तेजी से बढ़ता है। और कुछ मान n = n 0 के लिए एक क्षण आएगा जब स्थिरांकों में अंतर का प्रभाव समाप्त हो जाएगा और भविष्य में फ़ंक्शन c 2 nLog 2 n किसी भी n > n 0 के लिए c 1 n 2 से कम होगा।

इसे प्रदर्शित करने के लिए, दो कंप्यूटरों पर विचार करें - ए और बी। कंप्यूटर ए तेज़ है और सॉर्टिंग एल्गोरिदम चलाता है, और कंप्यूटर बी धीमा है और मर्ज सॉर्ट एल्गोरिदम चलाता है। दोनों कंप्यूटरों को दस लाख संख्याओं वाले एक सेट को सॉर्ट करना होगा। मान लीजिए कि कंप्यूटर ए प्रति सेकंड एक अरब ऑपरेशन करता है, और कंप्यूटर बी केवल दस मिलियन, वहां ए बी की तुलना में 100 गुना तेज चल रहा है। अंतर को और अधिक ध्यान देने योग्य बनाने के लिए, मान लें कि सक्षम विधि के लिए कोड सर्वश्रेष्ठ द्वारा लिखा गया था दुनिया में प्रोग्रामर प्रोसेसर को निर्देशों का उपयोग करते हैं, और इस एल्गोरिदम के साथ एन संख्याओं को सॉर्ट करने के लिए आपको 2 एन 2 ऑपरेशन (यानी, सी 1 = 2) करने की आवश्यकता होती है। कंप्यूटर बी पर मर्ज सॉर्ट एक नौसिखिया प्रोग्रामर द्वारा उच्च-स्तरीय भाषा का उपयोग करके लिखा गया था और परिणामी कोड के लिए 50nlog 2 n ऑपरेशन (यानी, c 2 = 50) की आवश्यकता होती है। इस प्रकार, दस लाख संख्याओं को क्रमबद्ध करने के लिए कंप्यूटर A की आवश्यकता होगी

और कंप्यूटर बी के लिए -

इसलिए, ऐसे कोड का उपयोग करना जिसका रनिंग समय अधिक धीरे-धीरे बढ़ता है, यहां तक ​​कि खराब कंप्यूटर और खराब कंपाइलर के साथ भी, बहुत कम सीपीयू समय की आवश्यकता होती है! 10,000,000 अंकों को सॉर्ट करने के लिए, मर्ज सॉर्ट का लाभ और भी अधिक ध्यान देने योग्य हो जाता है: जबकि समावेश सॉर्ट के लिए ऐसे कार्य के लिए लगभग 2.3 दिन की आवश्यकता होती है, तो मर्ज सॉर्ट के लिए 20 मिनट से भी कम समय लगता है। सामान्य नियम यह है कि सॉर्ट करने के लिए तत्वों की संख्या जितनी अधिक होगी, मर्ज सॉर्ट का लाभ उतना ही अधिक होगा। उपरोक्त उदाहरण दर्शाता है कि एल्गोरिदम, कंप्यूटर सॉफ़्टवेयर की तरह हैं तकनीकी. समग्र सिस्टम प्रदर्शन एल्गोरिदम की दक्षता पर उतना ही निर्भर करता है जितना कि हार्डवेयर की शक्ति पर।

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

एल्गोरिदम में निम्नलिखित विशेषताएं हैं:

ए) जटिलता;

बी) श्रम तीव्रता;

ग) विश्वसनीयता, आदि।

एल्गोरिदम की जटिलता का आकलन करने के लिए कई मानदंड हैं। सबसे अधिक बार हमें दिलचस्पी होगी विकास क्रमइनपुट डेटा की मात्रा बढ़ने पर समस्या को हल करने के लिए आवश्यक समय और मेमोरी क्षमता। आइए हम प्रत्येक विशिष्ट कार्य के साथ एक निश्चित संख्या को संबद्ध करें जिसे उसका कहा जाता है आकार. उदाहरण के लिए, मैट्रिक्स गुणन समस्या का आकार कारक मैट्रिक्स का सबसे बड़ा आकार हो सकता है; किसी ग्राफ़ पर किसी समस्या का आकार किसी दिए गए ग्राफ़ के किनारों की संख्या आदि हो सकता है।

किसी एल्गोरिथम द्वारा समस्या के आकार के फ़ंक्शन के रूप में लिया गया समय कहलाता है समय की जटिलतायह एल्गोरिथम. समस्या का आकार बढ़ने पर सीमा में इस जटिलता के व्यवहार को कहा जाता है स्पर्शोन्मुख समय जटिलता. इसी प्रकार परिभाषित किया गया है कैपेसिटिव जटिलताऔर स्पर्शोन्मुख क्षमता जटिलता.

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

4.1.1. फ़्रेम और फ़्रेम मशीनें*

दो कारों पर विचार करें:

1. मेमोरी तक रैंडम एक्सेस वाली मशीनें (इक्वल एक्सेस एड्रेस मशीन - रैम) एक योजक के साथ एक कंप्यूटर को मॉडल करती हैं, जिसमें प्रोग्राम निर्देश स्वयं को नहीं बदल सकते हैं।

2. संग्रहीत प्रोग्राम मॉडल एक मशीन है जिसमें मेमोरी तक यादृच्छिक पहुंच और निर्देशों को संशोधित करने की क्षमता (रैम*) है।

चित्र.2.9 रैम मशीनों की संरचना (रैम*)

रैम के लिए, प्रोग्राम को मेमोरी में नहीं लिखा जाता है, इसलिए प्रोग्राम स्वयं को संशोधित नहीं करता है। एक प्रोग्राम लेबल किए गए आदेशों का एक क्रम है। अंकगणितीय निर्देश, I/O निर्देश, अप्रत्यक्ष संबोधन निर्देश और शाखा निर्देश हैं। सभी गणनाएं रजिस्टर आर 0 (एडर) में की जाती हैं, जो किसी भी अन्य मेमोरी रजिस्टर की तरह, एक मनमाना पूर्णांक संग्रहीत कर सकता है। प्रत्येक कमांड में दो भाग होते हैं - एक ऑपरेशन कोड और एक पता। PAM कमांड असेंबली भाषा कमांड का एक सबसेट हैं; इस उपसमुच्चय को इच्छानुसार विस्तारित किया जा सकता है, लेकिन कार्यों की जटिलता का क्रम नहीं बदलेगा।

ऑपरेंड निम्न प्रकारों में से एक हो सकता है:

1. =मैंमतलब पूर्ण संख्या ही मैंऔर शाब्दिक कहा जाता है;

2. मैं- सामग्री पंजीकृत करें मैं (मैंगैर-नकारात्मक होना चाहिए);

3. *मैंइसका अर्थ है अप्रत्यक्ष संबोधन, अर्थात ऑपरेंड का मूल्य रजिस्टर की सामग्री है जे,कहाँ जे- एक पूर्णांक जो रजिस्टर में है मैं;अगर जे<0, कार रुकती है.

आप प्रोग्राम का मूल्य निर्धारित कर सकते हैं आरदो वस्तुओं का उपयोग करना: गैर-नकारात्मक पूर्णांकों के एक सेट से पूर्णांकों के एक सेट तक मैपिंग सी और एक "कमांड काउंटर", जो निष्पादित होने वाले अगले कमांड को निर्धारित करता है। फ़ंक्शन c है मेमोरी डिस्प्ले,अर्थात् सी(आई)-रजिस्टर संख्या में निहित पूर्णांक मैं (सामग्रीपंजीकरण करवाना मैं).

शुरू में с(i)=0सभी के लिए मैं 0 , प्रोग्राम काउंटर पी में पहले निर्देश पर सेट है, और आउटपुट टेप खाली है। निष्पादन के बाद कवें टीम से आरकाउंटर स्वचालित रूप से चालू हो जाता है (के+1)-वें (अर्थात्, अगले तक) आदेश, यदि क-मेरी टीम JUMP, HALT, JGTZ वगैरह जैसी टीम नहीं थी।

RAM* प्रोग्राम मेमोरी रजिस्टर में स्थित होता है। प्रत्येक RAM* कमांड दो लगातार मेमोरी रजिस्टरों पर कब्जा करता है: पहले रजिस्टर में ऑपरेशन कोड होता है, दूसरे में - पता। RAM* के लिए निर्देशों का सेट अप्रत्यक्ष पते को छोड़कर हर चीज़ में RAM के लिए संबंधित सेट से मेल खाता है, जिसे बाहर रखा गया है: RAM* प्रोग्राम निष्पादन के दौरान निर्देशों को बदलकर अप्रत्यक्ष पते का अनुकरण कर सकता है।

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

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

एल्गोरिथम की प्रभावशीलता का मूल्यांकन करने के लिए, एक जटिलता फ़ंक्शन का उपयोग किया जाता है, जिसे O ("बड़े के बारे में" पढ़ें) दर्शाया गया है। वास्तव में, अन्य मूल्यांकन भी हैं, लेकिन उस स्तर पर जब एक छात्र विभिन्न एल्गोरिदम से परिचित होना शुरू कर रहा है, उनकी वास्तव में आवश्यकता नहीं है। जटिलता फ़ंक्शन उस पैटर्न को दर्शाता है जिसमें स्रोत डेटा या उनकी मात्रा के आधार पर प्रोग्राम निष्पादन समय बढ़ जाएगा।

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

मुख्य कार्य हैं:

एल ओ(1) - ऐसा जटिलता फ़ंक्शन इंगित करता है कि प्रोग्राम का चलने का समय किसी भी प्रारंभिक डेटा के लिए स्थिर है;

एल ओ (एन) - संचालन की संख्या एन के अनुपात में बढ़ती है (यहां एन या तो एक कार्य पैरामीटर या सरणी में तत्वों की संख्या हो सकती है)।

एल ओ (लॉग एन) - संचालन की संख्या एन के लघुगणक के अनुपात में बढ़ती है (यह वास्तव में जटिलता है, उदाहरण के लिए, एक क्रमबद्ध सरणी में किसी तत्व की खोज करते समय आधे की विधि)। जैसे-जैसे N परिमाण के क्रम से बढ़ता है, संचालन की संख्या एक से बदल जाती है। लघुगणक का आधार आमतौर पर निर्दिष्ट नहीं किया जाता है; हम विकास की प्रकृति (तेज़/धीमी) में रुचि रखते हैं, न कि समय के सटीक मान में।

l O(N2) - संचालन की संख्या N के वर्ग के अनुपात में बढ़ जाती है। सामान्य तौर पर, समस्या की जटिलता के आधार पर यह O(Nk) हो सकता है।

एल ओ(एन!) - फैक्टोरियल एन के अनुपात में संचालन की संख्या बढ़ जाती है।

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

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

उदाहरण: आइए एक प्रोग्राम की जटिलता का अनुमान लगाएं जो कीबोर्ड से एक सरणी में प्रवेश करता है और उसमें सबसे बड़ा तत्व ढूंढता है।

आइए संचालन की संख्या N+(N-1)+1=2N जोड़ें। अर्थात्, एक ऐसा स्थिरांक है कि किसी भी N के लिए संचालन की संख्या CN से अधिक नहीं होती है। इसलिए, एल्गोरिदम की जटिलता O(N) है।

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

एल्गोरिथ्म में निम्नलिखित चरण शामिल हैं:

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

सर्वोत्तम स्थिति में, इस एल्गोरिदम को N+2 संचालन (संपूर्ण सरणी का इनपुट, एकल तुलना, आउटपुट) की आवश्यकता होगी, सबसे खराब स्थिति में (जब ऐसा कोई तत्व नहीं है - 2N+1 संचालन)। यदि N एक बड़ी संख्या है, उदाहरण के लिए 106, तो एकता की उपेक्षा की जा सकती है। इसलिए, एल्गोरिथम की जटिलता O(N) है।

उदाहरण: आइए प्रतिस्थापन विधि का उपयोग करके लंबाई एल के शब्द एन्क्रिप्शन एल्गोरिदम की जटिलता फ़ंक्शन निर्धारित करें। मान लीजिए कि एक तालिका है जिसमें वर्णमाला के प्रत्येक वर्ण के लिए वह वर्ण लिखा है जिससे उसे प्रतिस्थापित किया जाना चाहिए। आइए वर्णमाला S के अक्षरों की संख्या को निरूपित करें।

एल्गोरिथ्म में निम्नलिखित चरण शामिल हैं:

सभी वर्णों के माध्यम से एक शब्द (एक ऑपरेशन) लूप दर्ज करना

1. प्रत्येक वर्ण के लिए, तालिका में उसका प्रतिस्थापन ढूंढें (यदि तालिका क्रमबद्ध नहीं है और उसमें कोई गुण नहीं है जो खोज को सुविधाजनक बनाता है, तो सबसे खराब स्थिति में एक वर्ण के लिए एस ऑपरेशन होते हैं यदि खोजा गया तत्व बिल्कुल पर है) अंत)

2. पाए गए प्रतीक का आउटपुट

चक्र का अंत

ऑपरेशनों की कुल संख्या 1+(S+1)*L है। पर्याप्त रूप से बड़ी एस और एल इकाइयों के मामले में उपेक्षा की जा सकती है, यह पता चलता है कि इस एल्गोरिदम का जटिलता फ़ंक्शन ओ (एस * एल) है।

उदाहरण: आइए प्राकृतिक संख्या एन को बाइनरी नंबर सिस्टम (डेटा इनपुट और आउटपुट ऑपरेशंस के बिना) में परिवर्तित करने के लिए एल्गोरिदम की जटिलता फ़ंक्शन को परिभाषित करें।

एल्गोरिथ्म में निम्नलिखित चरण शामिल हैं:

तब तक लूप करें जब तक किसी संख्या को 2 से विभाजित करने पर परिणाम 0 न आ जाए

1. संख्या को 2 से विभाजित करें और शेषफल याद रखें

2. विभाजन के परिणाम को एक नई संख्या के रूप में लें

चक्र का अंत

संचालन की कुल संख्या 1+log2N से अधिक नहीं है। इसलिए, इस एल्गोरिदम में O(लॉग एन) की जटिलता है।

यदि किसी प्रोग्राम में अलग-अलग जटिलता वाले कार्यों वाले कई भाग होते हैं, तो हेबड़ा जटिलता फ़ंक्शन छोटे को "अवशोषित" करेगा। उदाहरण के लिए, यदि आप O(N) ऐरे इनपुट, O(N2) सॉर्ट, और ऑर्डर किए गए ऐरे का O(N) आउटपुट करते हैं, तो आप कह सकते हैं कि पूरे प्रोग्राम में O(N2) जटिलता है।

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

प्रशन

इन कार्यों का उपयोग प्रस्तुत सामग्री पर स्व-परीक्षण के लिए किया जाता है और ये अनिवार्य नहीं हैं।

1. द्विघात समीकरण को हल करने के लिए एल्गोरिदम की जटिलता फ़ंक्शन निर्धारित करें।

2. भुजाओं की दी गई संख्या के आधार पर एक नियमित बहुभुज बनाने के लिए एल्गोरिदम की जटिलता फ़ंक्शन निर्धारित करें।

3. किसी दिए गए स्थान पर किसी तत्व को किसी सरणी में डालने के लिए एल्गोरिदम की जटिलता फ़ंक्शन का निर्धारण करें (दाईं ओर एक स्थिति से अधिक या उसके बराबर संख्या वाले सभी तत्वों की प्रारंभिक शिफ्ट के साथ)।

4. एक कॉलम में दो प्राकृतिक संख्याओं को जोड़ने के लिए एल्गोरिदम की जटिलता फ़ंक्शन निर्धारित करें (मान लीजिए A पहली संख्या के अंकों की संख्या है, B दूसरी संख्या के अंकों की संख्या है)।

5. एक कॉलम में दो प्राकृतिक संख्याओं को गुणा करने के लिए एल्गोरिदम की जटिलता फ़ंक्शन निर्धारित करें।