Python के माध्यम से कोड की जटिलता का विश्लेषण

किसी एल्गोरिदम की कॉम्प्लेक्सिटी उस समय और/या स्पेस का माप है जिसकी आवश्यकता किसी दिए गए आकार (n) के इनपुट के लिए उस एल्गोरिदम को होती है। एल्गोरिदम की कॉम्प्लेक्सिटी कुछ विशेष कारकों पर निर्भर करती है, जैसे: कंप्यूटर की आर्किटेक्चर यानी हार्डवेयर प्लेटफ़ॉर्म, Abstract Data Type (ADT) का निरूपण, कम्पाइलर की दक्षता, अंतर्निहित एल्गोरिदम की जटिलता, और इनपुट का आकार। हालांकि, आप देखेंगे कि सबसे महत्वपूर्ण कारक आमतौर पर अंतर्निहित एल्गोरिदम की जटिलता और इनपुट का आकार होते हैं।

DataCamp के ब्लॉग Python Data Structures Tutorial में आप डेटा स्ट्रक्चर का बुनियादी अवलोकन और Python में उनके इम्प्लीमेंटेशन के बारे में सीख सकते हैं। यह ब्लॉग पोस्ट Python के मूलभूत डेटा स्ट्रक्चर का परिचय देता है। इसके साथ, आप Abstract Data Type और Data Structure, Primitive Data Structure और Non-Primitive Data Structure के बारे में जानेंगे।

एसिम्प्टोटिक विश्लेषण

एसिम्प्टोटिक विश्लेषण किसी भी कोड या ऑपरेशन के रनिंग टाइम की गणना को कम्प्यूटेशन की गणितीय इकाई में संदर्भित करता है। इसका संचालन f(n) जैसी किसी फ़ंक्शन के रूप में व्यक्त किया जाता है। गणितीय विश्लेषण में, एसिम्प्टोटिक विश्लेषण, जिसे asymptotics भी कहा जाता है, सीमित व्यवहार का वर्णन करने की एक विधि है।

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

एसिम्प्टोटिक नोटेशन

एल्गोरिदम की रनिंग टाइम कॉम्प्लेक्सिटी की गणना के लिए आम तौर पर प्रयुक्त नोटेशन निम्न हैं:

• Big O नोटेशन
• Big θ नोटेशन
• Big Ω नोटेशन

बिग ओह नोटेशन, Ο

Big O का उपयोग किसी एल्गोरिदम के प्रदर्शन या कॉम्प्लेक्सिटी को मापने के लिए किया जाता है। अधिक गणितीय रूप में, यह किसी फ़ंक्शन की ग्रोथ रेट की ऊपरी सीमा है; अर्थात यदि कोई फ़ंक्शन g(x), फ़ंक्शन f(x) से तेज़ी से नहीं बढ़ता, तो g को O(f) का सदस्य कहा जाता है। सामान्यतः, इसका उपयोग एल्गोरिदम की ऊपरी सीमा व्यक्त करने के लिए किया जाता है, जो सबसे खराब समय जटिलता या एल्गोरिदम द्वारा संभवतः लिया जाने वाला सबसे लंबा समय बताती है।

बिग ओमेगा नोटेशन, Ω

Ω(n) नोटेशन किसी एल्गोरिदम के रनिंग टाइम की निचली सीमा व्यक्त करने का औपचारिक तरीका है। यह सर्वोत्तम स्थिति की समय जटिलता या एल्गोरिदम द्वारा संभवतः लिया जाने वाला न्यूनतम समय मापता है।

बिग थीटा नोटेशन, θ

θ(n) नोटेशन किसी एल्गोरिदम के रनिंग टाइम की निचली और ऊपरी दोनों सीमाओं को व्यक्त करने का औपचारिक तरीका है।

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

अधिकतर Big O नोटेशन का उपयोग किया जाता है, और इसे प्रायः सभी समय एल्गोरिदम की ऊपरी सीमा खोजने के लिए प्रयोग किया जाता है, जबकि Big θ नोटेशन का कभी-कभी औसत स्थिति का पता लगाने के लिए उपयोग किया जाता है, और Ω नोटेशन इन तीनों में सबसे कम प्रयुक्त है।

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

उदाहरण के लिए क्विक सॉर्ट:

Quick sort एक Divide and Conquer एल्गोरिदम है जिसका उपयोग सॉर्टिंग के लिए किया जाता है। यह तत्वों को क्रम में रखने की एक व्यवस्थित विधि प्रदान करता है, जैसे कि किसी array में संख्याओं या तत्वों को आरोही या अवरोही क्रम में व्यवस्थित करना। यह एल्गोरिदम दिए गए array से एक pivot या इंडेक्स चुनता है। पिवट अलग-अलग तरीकों से चुना जा सकता है। नीचे दिए गए उदाहरण में पिवट के रूप में अंतिम तत्व चुना गया है।

Quick sort का मुख्य सार partition है। किसी array से एक partition तत्व चुना जाता है, फिर उस partition तत्व (जैसे pit) को सही स्थान पर रखा जाता है, और partition से बड़े तत्वों को pit के दाईं ओर तथा छोटे तत्वों को pit के बाईं ओर रखा जाता है।

#The last element will be taken as a pivot by the use of the function
#The smaller element is placed left to the pivot
#The greater element is placed to the right of the pivot
def partition(array,low,high):
    i = ( low-1 )         # index of smaller element is chosen
    pivot = array[high]     # pivot is chosen

    for j in range(low , high):

        #Is the element less or equal to the pivot
        if   array[j] <= pivot:

            # increment index of smaller element
            i = i+1
            array[i],array[j] = array[j],array[i]

    array[i+1],array[high] = array[high],array[i+1]
    return ( i+1 )

# The main crux of the problem that implements Quick sort is
#array[] is to be sorted
#high is the ending index
#low is the starting index

# Function to do Quick sort
def quickSort(array,low,high):
    if low < high:

       #pit is the partitioning index
        pit = partition(array,low,high)

      #Element sorted before and after partition
        quickSort(array, low, pit-1)
        quickSort(array, pit+1, high)

array=[2,4,6,8,10,12]
n = len(array)
quickSort(array,0,n-1)
print ("The Sorted array is:")
for i in range(n):
    print ("%d" %array[i]),

सॉर्ट किया गया array है:
2
4
6
8
10
12
आपको यह आउटपुट मिलेगा:

सॉर्ट किया गया array है: 2 4 6 8 10 12

अब समय है टाइम कॉम्प्लेक्सिटी का विश्लेषण करने का। सबसे पहले,

• सर्वोत्तम स्थिति: Ω(n log(n))
• औसत स्थिति: Θ(n log(n))
• सबसे खराब स्थिति: O(n^2)

अब, उपरोक्त कोड का विश्लेषण करें।

Best Case: यह वह स्थिति है जहाँ partition तत्व बीच वाले तत्व को पिवट के रूप में चुनता है। यानी एल्गोरिदम पहले और दूसरे आधे पर पुनरावर्ती रूप से कॉल करेगा। इसलिए—कुल आवश्यक चरणों की संख्या उतनी होगी जितना समय n से 1 तक पहुँचने में लगेगा यदि आप हर चरण में समस्या को 2 से विभाजित करते हैं। तो, n/2/2/2/2/..../2=1 *k बार। लेकिन ध्यान दें कि वास्तविक समीकरण है: n / 2^k = 1। क्योंकि 2^logn = n, हमें k = logn मिलता है। इसलिए एल्गोरिदम को आवश्यक चरणों (iterations) की संख्या O(log n) है, जिससे कुल एल्गोरिदम O(n log n) बनता है—क्योंकि प्रत्येक iteration O(n) है।

Average case: औसत स्थिति निकालने के लिए हमें array के सभी permutations पर विचार करना होता है और हर permutation के लिए लगने वाला समय निकालना होता है। आप इसे यहाँ और देख सकते हैं: Merge sort.

Worst case: सबसे खराब स्थिति में, यदि पहला तत्व पिवट चुना जाता है, तो जब इनपुट पहले से बढ़ते या घटते क्रम में हो, Worst case कॉम्प्लेक्सिटी मिलती है। सबसे खराब स्थिति का कारण यह है कि partitioning के बाद एक भाग का आकार 1 होगा और दूसरे का n-1। यहाँ, T(n) फ़ंक्शन है: यानी n तत्वों को क्विक सॉर्ट करने का समय T(n) = n तत्वों को partition करने का समय O(n) + n-1 तत्वों को क्विक सॉर्ट करने का समय T(n-1)। अतः, T(n) = T(n-1) + O(n) => T(n) = O(n^2)

उदाहरण

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

print('I love Python');

Hello world!
उपरोक्त एल्गोरिदम की टाइम कॉम्प्लेक्सिटी O(1) है क्योंकि यह हमेशा एक ही चरण लेता है। यह constant time है।

stuffs= ['eggs','toothbrush','kittens','mugs']
for stuff in stuffs:
    print("Here's a stuff: {}".format(stuff));

Here's a stuff: eggs Here's a stuff: toothbrush Here's a stuff: kittens Here's a stuff: mugs आप उपरोक्त एल्गोरिदम की दक्षता को Big O नोटेशन में कैसे वर्णित करेंगे?

उपरोक्त एल्गोरिदम का विश्लेषण करने के लिए, आपको यह तथ्य देखना होगा कि यह एल्गोरिदम कितने चरण लेता है। इस मामले में, सूची में चार आइटम हैं, और आपको प्रत्येक को एक-एक बार प्रिंट करना है। लेकिन अब सोचें, यदि सूची में 4 से अधिक, जैसे 15 आइटम हों, तो क्या for लूप 15 आइटम के लिए भी उतने ही चरण लेगा? चूँकि यह for लूप तत्वों की संख्या जितने चरण लेता है, आपको कहना चाहिए कि एल्गोरिदम की दक्षता O(1) के बजाय O(N) है।

अगला उदाहरण यह जाँचने के लिए एक सरल Python-आधारित एल्गोरिदम है कि कोई संख्या प्राइम है या नहीं:

def is_prime(number):   
    for i in range(2, number):       
        if number % 2 == 0:           
            return True   
    return False

उपरोक्त कोड एक संख्या को आर्ग्युमेंट के रूप में लेता है और एक for लूप शुरू करता है जिसमें आप 2 से लेकर उस संख्या तक हर संख्या से भाग देकर देखते हैं कि शेष बचता है या नहीं। यदि शेष नहीं बचता, तो आपको पता होता है कि संख्या प्राइम नहीं है और आप तुरंत False लौटाते हैं। यदि आप पूरी संख्या तक पहुँच जाते हैं और हर बार शेष मिलता है, तो आप जानते हैं कि संख्या प्राइम है और आप True लौटाते हैं।

आप उपरोक्त एल्गोरिदम की दक्षता O(N) निर्धारित कर सकते हैं। यह उदाहरण array या list के रूप में डेटा नहीं लेता, बल्कि संख्या आर्ग्युमेंट के रूप में पास होती है। यदि आप 11 जैसी कोई मनमानी संख्या पास करते हैं, तो for लूप लगभग ग्यारह चरण चलता है। (वास्तव में यह नौ चरण चलता है, क्योंकि यह दो से शुरू होता है और वास्तविक संख्या से ठीक पहले तक चलता है।) संख्या 101 के लिए, लूप लगभग 101 चरण चलता है। चूँकि चरणों की संख्या फ़ंक्शन में पास की गई संख्या के साथ समान अनुपात में बढ़ती है, यह O(N) का क्लासिक उदाहरण है।

def twoForLoops(n):
    for i in range(1,n):
        print("Printing:"+i);
    for i in range(1,100):
        print("Printing:"+i);

उपरोक्त कोड में एल्गोरिदम की कॉम्प्लेक्सिटी O(N) है। क्योंकि दूसरे लूप में 100 एक आर्ग्युमेंट है जिसे नज़रअंदाज़ किया जा सकता है, चूँकि जटिलता व्यक्त करते समय N को बहुत बड़ा मानकर चला जाता है।

def twoConditionalLoops(m,n):
    for i in range(0,m):
        print("Printing:"+i);
    for i in range(0,n):
        print("Printing:"+i);

यहाँ दो लूप हैं जहाँ एक लूप की लंबाई m है और दूसरे की लंबाई n। साथ ही, आपको m और n को बड़ा मानना चाहिए और तब ऑपरेशन की जटिलता O(n+m) होगी। चूँकि लूप अलग-अलग हैं और वे अलग इनपुट लेते हैं, जटिलता प्रकृति में additive है।

def twoNestedForLoops(int m,int n):
    for i in range(0,n):
        for j in range(0,m):
            print("Printing:"+(i*j));

यह एक nested for लूप है, और फिर से आपको n और m को बड़ा मानना चाहिए, तब ऑपरेशन की जटिलता O(n*m) होगी। चूँकि लूप समान हैं और nested हैं, जटिलता प्रकृति में multiplicative है।

बधाई!

आप इस ट्यूटोरियल के अंत तक पहुँच गए हैं! इस दौरान, आपने एसिम्प्टोटिक नोटेशन के साथ-साथ प्रोग्रामर और डेटा वैज्ञानिकों द्वारा उपयोग किए जाने वाले एक बुनियादी टूल के बारे में सीखा। आपने जटिलता का विश्लेषण करने का एक सरल और आसान तरीका सीखा है जो साधारण अंग्रेज़ी में लिखा गया है जहाँ तकनीकी शब्द और गणितीय कठोरता नहीं दी गई है। यद्यपि डेटा स्ट्रक्चर और एल्गोरिदम के विषय अक्सर तभी पढ़े और सिखाए जाते हैं जब आप कंप्यूटर साइंस के स्नातक या संबंधित क्षेत्र में हों, फिर भी इस विषय का बुनियादी ज्ञान होना समान रूप से महत्वपूर्ण है, यानी विशेषज्ञ होना आवश्यक नहीं। सीखने की यात्रा में गहराई तक जाने के लिए, आप इस लिंक को देख सकते हैं: MIT opencourseware Algorithm course

यदि आप Python के बारे में और सीखना चाहते हैं, तो ये DataCamp कोर्स देखें: