पायथन उदाहरणों के साथ बिग ओ नोटेशन और एल्गोरिथम विश्लेषण

परिचय

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

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

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

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

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

def fact(n):
    product = 1
    for i in range(n):
        product = product * (i+1)
    return product

print(fact(5))

ध्यान दें कि एल्गोरिथ्म केवल एक पूर्णांक को एक तर्क के रूप में लेता है। के अंदर fact() नाम का एक चर कार्य करें product के लिए प्रारंभ किया गया है 1. से एक लूप निष्पादित होता है 1 सेवा मेरे n और प्रत्येक पुनरावृत्ति के दौरान, में मान product लूप द्वारा पुनरावृत्त होने वाली संख्या से गुणा किया जाता है और परिणाम में संग्रहीत किया जाता है product फिर से परिवर्तनशील। लूप निष्पादित होने के बाद, product वेरिएबल में फैक्टोरियल होगा।

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

def fact2(n):
    if n == 0:
        return 1
    else:
        return n * fact2(n-1)

print(fact2(5))

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

जुपिटर नोटबुक में, आप का उपयोग कर सकते हैं %timeit फ़ंक्शन को निष्पादित करने के लिए फ़ंक्शन द्वारा लिए गए समय को खोजने के लिए फ़ंक्शन कॉल के बाद शाब्दिक:

%timeit fact(50)

यह हमें देगा:

9 µs ± 405 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

आउटपुट कहता है कि एल्गोरिथ्म लेता है 9 माइक्रोसेकंड (प्लस/माइनस 45 नैनोसेकंड) प्रति लूप।

इसी तरह, हम गणना कर सकते हैं कि दूसरे दृष्टिकोण को निष्पादित करने में कितना समय लगता है:

%timeit fact2(50)

यह परिणाम होगा:

15.7 µs ± 427 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

रिकर्सन को शामिल करने वाला दूसरा एल्गोरिदम लेता है 15 माइक्रोसेकंड (प्लस/माइनस 427 नैनोसेकंड)।

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

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

बिग-ओ नोटेशन के साथ एल्गोरिदम विश्लेषण

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

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

उदाहरण के लिए, यदि कोई है रैखिक संबंध इनपुट और एल्गोरिथम द्वारा इसके निष्पादन को पूरा करने के लिए उठाए गए कदम के बीच, इस्तेमाल किया जाने वाला बिग-ओ नोटेशन होगा पर). इसी तरह, के लिए बिग-ओ नोटेशन द्विघात कार्य is ओ (एन²).

अंतर्ज्ञान का निर्माण करने के लिए:

• पर): पर n=1, 1 कदम उठाया जाता है। पर n=10, 10 कदम उठाए गए हैं।
• ओ (एन²): पर n=1, 1 कदम उठाया जाता है। पर n=10, 100 कदम उठाए गए हैं।

At n=1, ये दोनों एक ही प्रदर्शन करेंगे! यह एक और कारण है कि इनपुट और उस इनपुट को संसाधित करने के लिए चरणों की संख्या के बीच संबंध को देखना कुछ ठोस इनपुट के साथ कार्यों का मूल्यांकन करने से बेहतर है।

निम्नलिखित कुछ सबसे सामान्य बिग-ओ फ़ंक्शन हैं:

नाम	बड़ा हे
स्थिर	ओ (सी)
रैखिक	पर)
द्विघात	ओ (एन²)
घन	ओ (एन³)
घातीय	हे(2ⁿ)
लघुगणक	O (लॉग (n))
लॉग लीनियर	ओ (एनलॉग (एन))

आप इन कार्यों की कल्पना कर सकते हैं और उनकी तुलना कर सकते हैं:

आम तौर पर बोलना - रैखिक से भी बदतर कुछ भी खराब जटिलता (यानी अक्षम) माना जाता है और यदि संभव हो तो इससे बचा जाना चाहिए। रैखिक जटिलता ठीक है और आमतौर पर एक आवश्यक बुराई है। लॉगरिदमिक अच्छा है। निरंतर अद्भुत है!

बिग-ओ की गणना कैसे की जाती है, इसका अंदाजा लगाने के लिए, आइए स्थिर, रैखिक और द्विघात जटिलता के कुछ उदाहरण देखें।

लगातार जटिलता - ओ (सी)

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

आइए पायथन में एक सरल एल्गोरिदम लिखें जो सूची में पहले आइटम का वर्ग ढूंढता है और फिर इसे स्क्रीन पर प्रिंट करता है:

def constant_algo(items):
    result = items[0] * items[0]
    print(result)

constant_algo([4, 5, 6, 8])

उपरोक्त लिपि में, इनपुट आकार के बावजूद, या इनपुट सूची में मदों की संख्या items, एल्गोरिथ्म केवल 2 चरण निष्पादित करता है:

1. पहले तत्व का वर्ग ज्ञात करना
2. स्क्रीन पर परिणाम प्रिंट करना।

इसलिए, जटिलता स्थिर रहती है।

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

steps = []
def constant(n):
    return 1
    
for i in range(1, 100):
    steps.append(constant(i))
plt.plot(steps)

रैखिक जटिलता - पर)

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

इस उदाहरण में, आइए एक साधारण प्रोग्राम लिखें जो सूची में सभी आइटम्स को कंसोल पर प्रदर्शित करता है:

def linear_algo(items):
    for item in items:
        print(item)

linear_algo([4, 5, 6, 8])

की जटिलता linear_algo() उपरोक्त उदाहरण में फ़ंक्शन रैखिक है क्योंकि फॉर-लूप के पुनरावृत्तियों की संख्या होगी इनपुट के आकार के बराबर items सरणी. उदाहरण के लिए, यदि 4 आइटम हैं items सूची, फॉर-लूप को 4 बार निष्पादित किया जाएगा।

आइए x-अक्ष पर इनपुट की संख्या और y-अक्ष पर चरणों की संख्या के साथ रैखिक जटिलता एल्गोरिदम के लिए जल्दी से एक प्लॉट बनाएं:

steps = []
def linear(n):
    return n
    
for i in range(1, 100):
    steps.append(linear(i))
    
plt.plot(steps)
plt.xlabel('Inputs')
plt.ylabel('Steps')

यह परिणाम होगा:

ध्यान देने वाली एक महत्वपूर्ण बात यह है कि बड़े इनपुट के साथ, स्थिरांक मूल्य खो देते हैं। यही कारण है कि हम आम तौर पर बिग-ओ नोटेशन से स्थिरांक हटाते हैं, और ओ (2 एन) जैसे अभिव्यक्ति को आमतौर पर ओ (एन) तक छोटा कर दिया जाता है। O(2n) और O(n) दोनों रैखिक हैं - रैखिक संबंध वह है जो मायने रखता है, ठोस मूल्य नहीं। उदाहरण के लिए, आइए संशोधित करें linear_algo():

def linear_algo(items):
    for item in items:
        print(item)

    for item in items:
        print(item)

linear_algo([4, 5, 6, 8])

दो फॉर-लूप हैं जो इनपुट पर पुनरावृति करते हैं items सूची। इसलिए एल्गोरिथ्म की जटिलता बन जाती है ओ (2 एन), हालांकि इनपुट सूची में अनंत वस्तुओं के मामले में, अनंत का दोगुना अभी भी अनंत के बराबर है। हम स्थिरांक को अनदेखा कर सकते हैं 2 (चूंकि यह अंततः महत्वहीन है) और एल्गोरिथ्म की जटिलता बनी हुई है पर).

आइए एक्स-अक्ष पर इनपुट और वाई-अक्ष पर चरणों की संख्या को प्लॉट करके इस नए एल्गोरिदम की कल्पना करें:

steps = []
def linear(n):
    return 2*n
    
for i in range(1, 100):
    steps.append(linear(i))
    
plt.plot(steps)
plt.xlabel('Inputs')
plt.ylabel('Steps')

ऊपर की लिपि में, आप स्पष्ट रूप से देख सकते हैं कि वाई = 2एन, हालांकि, आउटपुट रैखिक है और इस तरह दिखता है:

द्विघात जटिलता - ओ (एन²)

एक एल्गोरिथ्म की जटिलता को द्विघात कहा जाता है जब एक एल्गोरिथ्म को निष्पादित करने के लिए आवश्यक कदम इनपुट में वस्तुओं की संख्या का एक द्विघात कार्य होता है। द्विघात जटिलता को के रूप में दर्शाया गया है ओ (एन²):

def quadratic_algo(items):
    for item in items:
        for item2 in items:
            print(item, ' ' ,item2)

quadratic_algo([4, 5, 6, 8])

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

निम्न ग्राफ़ द्विघात जटिलता वाले एल्गोरिथम के चरणों के विरुद्ध इनपुट की संख्या को प्लॉट करता है:

लघुगणकीय जटिलता - ओ (logn)

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

इसके लिए सरणी को क्रमबद्ध करने की आवश्यकता है, और हमारे लिए डेटा के बारे में एक धारणा बनाने के लिए (जैसे कि इसे क्रमबद्ध किया गया है)।

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

जटिल कार्यों की जटिलता ढूँढना?

पिछले उदाहरणों में, हमारे पास इनपुट पर काफी सरल कार्य थे। हालांकि, हम इनपुट पर अन्य कार्यों को कॉल करने वाले कार्यों के बिग-ओ की गणना कैसे करते हैं?

चलो एक नज़र डालते हैं:

def complex_algo(items):

    for i in range(5):
        print("Python is awesome")

    for item in items:
        print(item)

    for item in items:
        print(item)

    print("Big O")
    print("Big O")
    print("Big O")

complex_algo([4, 5, 6, 8])

ऊपर की स्क्रिप्ट में कई कार्य किए जा रहे हैं, सबसे पहले, कंसोल पर 5 बार एक स्ट्रिंग का उपयोग करके प्रिंट किया जाता है print बयान। अगला, हम स्क्रीन पर दो बार इनपुट सूची प्रिंट करते हैं, और अंत में, कंसोल पर तीन बार एक और स्ट्रिंग मुद्रित होती है। इस तरह के एल्गोरिदम की जटिलता को खोजने के लिए, हमें एल्गोरिदम कोड को भागों में तोड़ना होगा और अलग-अलग टुकड़ों की जटिलता को खोजने का प्रयास करना होगा। प्रत्येक टुकड़े की जटिलता को चिह्नित करें।

पहले खंड में हमारे पास है:

for i in range(5):
	print("Python is awesome")

इस भाग की जटिलता है ओ (5) चूंकि इनपुट के बावजूद कोड के इस टुकड़े में पांच निरंतर चरणों का प्रदर्शन किया जा रहा है।

अगला, हमारे पास है:

for item in items:
	print(item)

हम जानते हैं कि उपरोक्त कोड की जटिलता है पर). इसी तरह, निम्नलिखित कोड की जटिलता भी है पर):

for item in items:
	print(item)

अंत में, कोड के निम्नलिखित भाग में, एक स्ट्रिंग को तीन बार प्रिंट किया जाता है, इसलिए जटिलता है ओ (3):

print("Big O")
print("Big O")
print("Big O")

समग्र जटिलता को खोजने के लिए, हमें बस इन व्यक्तिगत जटिलताओं को जोड़ना होगा:

O(5) + O(n) + O(n) + O(3)

उपरोक्त को सरल बनाने पर हमें प्राप्त होता है:

O(8) + O(2n) = O(8+2n)

हमने पहले कहा था कि जब इनपुट (इस मामले में लंबाई n है) बहुत बड़ा हो जाता है, तो स्थिरांक महत्वहीन हो जाते हैं यानी अनंत का दोगुना या आधा अभी भी अनंत रहता है। इसलिए, हम स्थिरांक को अनदेखा कर सकते हैं। एल्गोरिथम की अंतिम जटिलता होगी पर)!

सबसे खराब बनाम सर्वश्रेष्ठ केस जटिलता

आमतौर पर, जब कोई आपसे एल्गोरिथम की जटिलता के बारे में पूछता है - तो वे सबसे खराब स्थिति वाली जटिलता (बिग-ओ) में रुचि रखते हैं। कभी-कभी, उन्हें सर्वोत्तम-केस जटिलता (बिग-ओमेगा) में भी दिलचस्पी हो सकती है।

इनके बीच के संबंध को समझने के लिए, आइए एक और कोड पर एक नज़र डालते हैं:

def search_algo(num, items):
    for item in items:
        if item == num:
            return True
        else:
            pass
nums = [2, 4, 6, 8, 10]

print(search_algo(2, nums))

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

सर्वोत्तम और सबसे खराब स्थिति जटिलता के अलावा, आप गणना भी कर सकते हैं औसत जटिलता (बिग-थीटा) एक एल्गोरिदम का, जो आपको बताता है कि "एक यादृच्छिक इनपुट दिया गया है, एल्गोरिदम की अपेक्षित समय जटिलता क्या है"?

अंतरिक्ष जटिलता

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

निम्नलिखित उदाहरण पर एक नजर डालें:

def return_squares(n):
    square_list = []
    for num in n:
        square_list.append(num * num)

    return square_list

nums = [2, 4, 6, 8, 10]
print(return_squares(nums))

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

निष्कर्ष

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