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

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

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

स्मृति या समय

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

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

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

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

हम अस्थायी जटिलता पर ध्यान केंद्रित करेंगे, लेकिन, फिर भी, हम निश्चित रूप से खपत की गई मेमोरी की मात्रा को निर्धारित करेंगे।

मूल्यांकन का आदेश दें

विभिन्न एल्गोरिदम की तुलना करते समय, यह जानना महत्वपूर्ण है कि इनपुट डेटा की मात्रा पर उनकी जटिलता कैसे निर्भर करती है। उदाहरण के लिए, जब एक विधि का उपयोग करके छंटनी की जाती है, तो एक हज़ार नंबरों को संसाधित करने में 1 s लगता है। और एक मिलियन नंबरों को संसाधित करने में 10 सेकंड लगते हैं, दूसरे एल्गोरिथम का उपयोग करते हुए, इसमें 2 s लग सकते हैं। और 5 एस। क्रमशः। ऐसी स्थितियों में असमान रूप से यह कहना असंभव है कि कौन सा एल्गोरिदम बेहतर है।

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

for i:=1 to N do

begin

max:=A[i,1];

for j:=1 to N do

begin

if A[i,j]>max then

max:=A[i,j]

end;

writeln(max);

end;





इस एल्गोरिथ्म में, वेरिएबल आई 1 से एन में बदलता है। आई के प्रत्येक परिवर्तन के साथ, वेरिएबल जे भी 1 से एन में बदलता है। बाहरी लूप के एन पुनरावृत्तियों में से प्रत्येक के दौरान, आंतरिक लूप भी एन बार निष्पादित करता है। आंतरिक लूप की पुनरावृत्तियों की कुल संख्या एन * एन है। यह O (N ^ 2) एल्गोरिथ्म की जटिलता को निर्धारित करता है।

एल्गोरिथम की जटिलता क्रम का अनुमान लगाते हुए, केवल उस भाग का उपयोग करना आवश्यक है जो सबसे तेजी से बढ़ता है। मान लें कि कर्तव्य चक्र को अभिव्यक्ति ^ ^ 3 + N द्वारा वर्णित किया गया है। इस स्थिति में, इसकी जटिलता O (N ^ 3) के बराबर होगी। फ़ंक्शन के तेजी से बढ़ते हिस्से पर विचार करने से हमें एन के साथ एल्गोरिदम के व्यवहार का मूल्यांकन करने की अनुमति मिलती है। उदाहरण के लिए, एन = 100 के साथ, एन ^ 3 + एन = 1000100 और एन = 1000000 के बीच का अंतर केवल 100 है, जो 0.01% है।

ओ की गणना करते समय, आप भावों में निरंतर कारकों को अनदेखा कर सकते हैं। 3N ^ 3 के एक कार्यशील चरण के साथ एक एल्गोरिथ्म को O (N ^ 3) माना जाता है। यह समस्या के आकार में परिवर्तन पर O (N) अनुपात की निर्भरता को और अधिक स्पष्ट करता है।

कठिनाई परिभाषा

एक कार्यक्रम के सबसे जटिल हिस्से आमतौर पर लूपिंग और कॉलिंग प्रक्रियाएं हैं। पिछले उदाहरण में, दो चक्रों का उपयोग करके संपूर्ण एल्गोरिथ्म का प्रदर्शन किया गया था।

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

एक उदाहरण के रूप में, दो प्रक्रियाओं पर विचार करें: जटिलता ओ (एन ^ 3) के साथ धीमा और जटिलता ओ (एन ^ 2) के साथ फास्ट।

procedure Slow;

var

i,j,k: integer;

begin

for i:=1 to N do

for j:=1 to N do

for k:=1 to N do

{- }

end;

procedure Fast;

var

i,j: integer;

begin

for i:=1 to N do

for j:=1 to N do

Slow;

end;

procedure Both;

begin

Fast;

end;





यदि स्लो प्रक्रिया को फास्ट प्रक्रिया के आंतरिक चक्रों में कहा जाता है, तो प्रक्रियाओं की जटिलता को गुणा किया जाता है। इस स्थिति में, एल्गोरिथ्म की जटिलता हे (N ^ 2) * O (N ^ 3) = O (N ^ 5)।

यदि मुख्य कार्यक्रम प्रक्रियाओं को बदले में बुलाता है, तो उनकी कठिनाइयां बढ़ जाती हैं: O (N ^ 2) + O (N ^ 3) = O (N ^ 3)। निम्नलिखित स्निपेट में ऐसी जटिलता है:

procedure Slow;

var

i,j,k: integer;

begin

for i:=1 to N do

for j:=1 to N do

for k:=1 to N do

{- }

end;

procedure Fast;

var

i,j: integer;

begin

for i:=1 to N do

for j:=1 to N do

{- }

end;

procedure Both;

begin

Fast;

Slow;

end;

पुनरावर्ती एल्गोरिदम की जटिलता

सरल पुनरावृत्ति

याद रखें कि पुनरावर्ती प्रक्रियाएं ऐसी प्रक्रियाएं हैं जो स्वयं को बुलाती हैं। उनकी कठिनाई निर्धारित करना काफी कठिन है। इन एल्गोरिदम की जटिलता न केवल आंतरिक छोरों की जटिलता पर निर्भर करती है, बल्कि पुनरावृत्ति की पुनरावृत्तियों की संख्या पर भी निर्भर करती है। एक पुनरावर्ती प्रक्रिया काफी सरल लग सकती है, लेकिन यह बार-बार खुद को आमंत्रित करके एक कार्यक्रम को गंभीरता से जटिल कर सकती है।

भाज्य संगणना के पुनरावर्ती कार्यान्वयन पर विचार करें:

function Factorial(n: Word): integer;

begin

if n > 1 then

Factorial:=n*Factorial(n-1)

else

Factorial:=1;

end;





इस प्रक्रिया को एन बार किया जाता है, इसलिए इस एल्गोरिथ्म की कम्प्यूटेशनल जटिलता ओ (एन) है।

एकाधिक पुनरावृत्ति

एक पुनरावर्ती एल्गोरिदम जो कई बार खुद को कॉल करता है, एकाधिक पुनरावृत्ति कहलाता है। ऐसी प्रक्रियाओं का विश्लेषण करना अधिक कठिन है, इसके अलावा, वे एल्गोरिथ्म को और अधिक जटिल बना सकते हैं।

निम्नलिखित प्रक्रिया पर विचार करें:

procedure DoubleRecursive(N: integer);

begin

if N>0 then

begin

DoubleRecursive(N-1);

DoubleRecursive(N-1);

end;

end;





चूंकि प्रक्रिया को दो बार कहा जाता है, इसलिए यह माना जा सकता है कि इसका कर्तव्य चक्र O (2N) = O (N) होगा। लेकिन वास्तव में स्थिति बहुत अधिक जटिल है। यदि आप सावधानीपूर्वक इस एल्गोरिथम की जांच करते हैं, तो यह स्पष्ट हो जाएगा कि इसकी जटिलता ओ (2 ^ (एन + 1) -1) = ओ (2 ^ एन) है। आपको हमेशा याद रखना चाहिए कि पुनरावर्ती एल्गोरिदम की जटिलता का विश्लेषण करना एक बहुत ही गैर-तुच्छ कार्य है।

पुनरावर्ती एल्गोरिदम की वॉल्यूमेट्रिक जटिलता

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

मध्यम और सबसे खराब मामला

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

function Locate(data: integer): integer;

var

i: integer;

fl: boolean;

begin

fl:=false; i:=1;

while (not fl) and (i<=N) do

begin

if A[i]=data then

fl:=true

else

i:=i+1;

end;

if not fl then

i:=0;

Locate:=I;

end;





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

दूसरी ओर, वांछित वस्तु पहले स्थान पर सूची में हो सकती है। एल्गोरिदम को केवल एक कदम उठाना होगा। ऐसे मामले को सबसे अच्छा कहा जाता है और इसकी जटिलता का अनुमान ओ (1) के रूप में लगाया जा सकता है।

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

इस मामले में, औसत और अपेक्षित जटिलता समान है, लेकिन कई एल्गोरिदम के लिए सबसे खराब स्थिति उम्मीद से बहुत अलग है। उदाहरण के लिए, सबसे खराब स्थिति त्वरित-सॉर्ट एल्गोरिथ्म में ओ (एन ^ 2) के आदेश की जटिलता है, जबकि अपेक्षित व्यवहार ओ (एन * लॉग (एन)) के अनुमान से वर्णित है, जो बहुत तेज है।

सामान्य कठिनाई मूल्यांकन कार्य

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

1. C एक स्थिरांक है

2.लॉग (लॉग (एन))

3. क्लॉग (एन)

4. एन ^ सी, 0 <सी <1

5. एन

6. एन * लॉग (एन)

7. एन ^ सी, सी> 1

8. सी ^ एन, सी> 1

9. एन!

यदि हम एक एल्गोरिथ्म की जटिलता का मूल्यांकन करना चाहते हैं, जिसकी जटिलता समीकरण में इन कार्यों में से कई शामिल हैं, तो समीकरण तालिका में नीचे स्थित एक फ़ंक्शन को कम किया जा सकता है। उदाहरण के लिए, O (लॉग (N) + N!) = O (N!)।

यदि एल्गोरिथ्म को कम मात्रा में डेटा के लिए बुलाया जाता है, तो O (N ^ 2) जटिलता को स्वीकार्य माना जा सकता है, लेकिन अगर एल्गोरिथ्म वास्तविक समय में काम करता है, तो O (N) प्रदर्शन हमेशा पर्याप्त नहीं होता है।

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

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