Ruby में बिग-O नोटेशन में मास्टर करें: एक व्यावहारिक गाइड

एक समय था जब "उसके लिए बिग-O नोटेशन क्या है?" प्रश्न सुनने से ज्यादा मुझे कुछ भी नहीं डराता था। मुझे स्कूल से यह विषय याद था, लेकिन क्योंकि इसका गणित से लेना-देना था (जो कभी मेरा सबसे मजबूत विषय नहीं था), मैंने इसे ब्लैक आउट कर दिया था।

हालांकि, जैसे-जैसे मेरा करियर आगे बढ़ा, मैंने खुद को पाया:

• परफॉरमेंस चार्ट्स देखते हुए
• धीमे क्वेरीज़ को डीबग करने की कोशिश करते हुए
• पूछा जा रहा है कि क्या मैंने इस बात पर विचार किया है कि बढ़े हुए लोड को देखते हुए मेरा कोड कैसे टिकेगा

जब मैंने तय किया कि बिग-O पर वापस सर्कल (समझ गए?) करने और सीखने का समय आ गया है, तो मुझे इसकी उच्च-स्तरीय सरलता पर आश्चर्य हुआ। मैं इस लेख में जो सीखा उसे साझा कर रहा हूं ताकि आप, मेरे साथी इंजीनियर, न केवल इंटरव्यू में उड़ते रंगों के साथ पास कर सकें, बल्कि परफॉरमेंट, स्केलेबल सिस्टम भी बना सकें।

मैं वादा करता हूं, बिग-O उतना डरावना नहीं है जितना लगता है। एक बार जब आप इसे समझ लेते हैं, तो आप किसी एल्गोरिदम को देख सकते हैं और प्रोफाइलिंग टूल चलाए बिना आसानी से इसकी दक्षता का पता लगा सकते हैं!

बिग-O नोटेशन क्या है?

बिग-O नोटेशन यह कहने का एक फैंसी तरीका है, "अरे, इस एल्गोरिदम के लिए सबसे खराब स्थिति का प्रदर्शन क्या है?" आपने किसी फंक्शन को O(n) या O(1) के रूप में वर्णित देखा होगा। इसका मतलब है:

• O(n) - सबसे खराब स्थिति का रन टाइम इनपुट आकार (n) बढ़ने के साथ रैखिक रूप से बढ़ता है
• O(1) - किसी भी आकार के इनपुट के लिए सबसे खराब स्थिति का रन टाइम स्थिर है

...और वास्तव में यह समझने के लिए कि इसका क्या अर्थ है, हमें एसिम्पटोट्स के बारे में सीखना होगा

एसिम्पटोट्स?

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

• सीमा विश्लेषण: यह देखना कि क्या होता है जब एक फंक्शन किसी मान के निकट पहुंचता है
• एसिम्पटोटिक विश्लेषण: यह देखना कि क्या होता है जब f(x) अनंत की ओर पहुंचता है

उदाहरण के लिए, मान लें कि हम फंक्शन f(x) = x^2 + 4x को प्लॉट करते हैं।

हम निम्नलिखित विश्लेषण कर सकते हैं: - सीमा विश्लेषण: जैसे-जैसे x बढ़ता है, f(x) अनंत की ओर पहुंचता है, इसलिए हम कह सकते हैं कि x के अनंत की ओर पहुंचने पर f(x) = x^2 + 4x की सीमा अनंत है। - एसिम्पटोटिक विश्लेषण: जैसे-जैसे x बहुत बड़ा होता जाता है, 4x पद x^2 पद की तुलना में महत्वहीन हो जाता है। तो हम कह सकते हैं कि f(x) = x^2 + 4x अनंत की ओर पहुंचने वाले x के मानों के लिए f(x) = x^2 के लगभग बराबर हो जाता है।

यह समझने के लिए कि हम कैसे कह सकते हैं कि एक फंक्शन का हिस्सा "महत्वहीन" हो जाता है, विचार करें कि जब आप मूल फंक्शन में अलग-अलग नंबर प्लग करते हैं तो क्या होता है। उदाहरण के लिए, जब x = 1, फंक्शन 1 + 4 (जो 5 के बराबर है) लौटाता है। हालांकि, जब x = 2,000, फंक्शन 4,000,000 + 8,000 (जो 4,008,000 के बराबर है) लौटाता है -- x^2 पद कुल में 4x की तुलना में बहुत अधिक योगदान दे रहा है।

बिग-O नोटेशन एक एल्गोरिदम के रन टाइम के इनपुट के आकार के रूप में कैसे बदलता है, इसका वर्णन करने का एक तरीका है।

एल्गोरिदम के रन टाइम को क्या निर्धारित करता है?

अगर मैं आपसे पूछूं कि घास के ढेर में सुई ढूंढने में आपको कितना समय लगेगा, तो मुझे लगता है कि आप जानना चाहेंगे कि ढेर में कितनी घास है। अगर मैं जवाब दूं "10 टुकड़े" तो मुझे यकीन है कि आप काफी आश्वस्त होंगे कि आप एक या दो मिनट के भीतर सुई ढूंढ सकते हैं, लेकिन अगर मैं कहूं "1,000 टुकड़े," तो आप शायद उतने उत्साहित नहीं होंगे।

एक और जानकारी है जो आपको पता होनी चाहिए। घास के प्रत्येक टुकड़े के जुड़ने पर ढेर को खोजने में कितना अधिक समय लगता है? और क्या होता है जब घास की मात्रा अनंत की ओर पहुंचती है?

यह उपरोक्त एसिम्पटोटिक विश्लेषण के उदाहरण के समान है। आइए एक और उदाहरण देखें बस यह सुनिश्चित करने के लिए कि हम सभी इसे समझ गए हैं। फंक्शन f(x) = 5x^2 + 100x + 50 पर विचार करें। हम इस फंक्शन के दो भागों को अलग-अलग प्लॉट कर सकते हैं:

पिछले उदाहरण की तरह, 5x^2 पद अंततः 100x + 50 पदों से बड़ा हो जाता है, इसलिए हम उन्हें छोड़ सकते हैं और कह सकते हैं कि f(x) = 5x^2 + 100x + 50 का रन टाइम x^2 के रूप में बढ़ता है।

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

लीनियर सर्च के लिए बिग-O ढूंढना

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

यहाँ Ruby में एक कार्यान्वयन है।

def find_number_via_linear_search(array, target)
  counter = 0
  # दिए गए ऐरे के माध्यम से पुनरावृति करें शुरू
  # इंडेक्स 0 पर और अंत तक जारी रखें
  while counter < array.length
    if array[counter] == target
      # यदि लक्ष्य तत्व मिला तो बाहर निकलें
      return "linear search took: #{counter} iterations"
    else
      counter += 1
    end
  end
  return "#{target} not found"
end

हम इस मेथड को ऐसे चला सकते हैं:

# 50 पूर्णांकों के साथ एक ऐरे बनाएं
# और फिर चीजों को अधिक दिलचस्प बनाने के लिए क्रम को पुनर्व्यवस्थित करें
array = [*1..50].shuffle
find_number_via_linear_search(array, 24)

मैंने इसे कुछ बार चलाया और निम्न परिणाम प्राप्त किए:

=> "linear search took: 10 iterations"
=> "linear search took: 11 iterations"
=> "linear search took: 26 iterations"

किसी फंक्शन के बिग-O नोटेशन का विश्लेषण करते समय, हम सबसे खराब स्थिति (उर्फ ऊपरी एसिम्पटोटिक बाउंड) की परवाह करते हैं।

इसके बारे में सहज रूप से सोचते हुए, पुनरावृत्तियों की सबसे छोटी संख्या 1 होगी। यह तब होता है जब लक्ष्य तत्व ऐरे में स्थिति 0 पर था। पुनरावृत्तियों की सबसे बड़ी संख्या (या सबसे खराब स्थिति) 50 होगी। यह तब होगा जब लक्ष्य तत्व ऐरे में नहीं मिला था।

यदि हमारे ऐरे में 100 तत्व हैं, तो सबसे खराब स्थिति 100 पुनरावृत्तियाँ होगी। 200 तत्व? 200 पुनरावृत्तियाँ। इस प्रकार, लीनियर सर्च के लिए बिग-O नोटेशन केवल O(n) है, जहां n तत्वों की संख्या है।

बाइनरी सर्च के साथ एक अधिक जटिल उदाहरण!

आइए अब बाइनरी सर्च पर विचार करें। यहाँ आप एक प्री-सॉर्टेड ऐरे का बाइनरी सर्च कैसे करते हैं: 1. मध्य तत्व लें
2. यदि element == target तो हम हो गए 3. यदि element > target तो ऐरे के ऊपरी आधे हिस्से को त्याग दें 4. यदि element < target तो ऐरे के निचले आधे हिस्से को त्याग दें 5. शेष ऐरे के साथ चरण 1 पर फिर से शुरू करें

नोट: यदि आप एक Rubyist हैं, तो एक बिल्ट-इन b-search मेथड है जो आपके लिए इस एल्गोरिदम को लागू करता है!

उदाहरण के लिए, मान लें कि आपके पास एक डिक्शनरी है और आप "पाइनएप्पल" शब्द खोज रहे हैं। हम डिक्शनरी के मध्य पृष्ठ पर जाएंगे। यदि इसमें "पाइनएप्पल" शब्द होता, तो हम हो जाते!

लेकिन मेरा अनुमान है, डिक्शनरी का मध्य अभी तक "p" में नहीं होगा तो शायद हमें "लामा" शब्द मिलेगा। अक्षर "L" "P" से पहले आता है इसलिए हम डिक्शनरी के पूरे निचले आधे हिस्से को त्याग देंगे। अगला, हम जो बचा है उसके साथ प्रक्रिया को दोहराएंगे।

लीनियर सर्च की तरह, बाइनरी सर्च के लिए सर्वश्रेष्ठ स्थिति का रन टाइम एक पुनरावृत्ति है। लेकिन सबसे खराब स्थिति क्या है? यहाँ एक उदाहरण ऐरे है जिसमें 16 तत्व हैं -- मान लें कि हम संख्या 23 खोजने के लिए बाइनरी सर्च का उपयोग करना चाहते हैं:

[2, 3, 15, 18, 22, 23, 24, 50, 65, 66, 88, 90, 92, 95, 100, 200]

पहला चरण इंडेक्स 7 पर संख्या को देखना होगा, जो 50 है। चूंकि 50, 23 से बड़ा है, हम दाईं ओर सब कुछ त्याग देते हैं। अब हमारा ऐरे ऐसा दिखता है:

[2, 3, 15, 18, 22, 23, 24, 50]

मध्य तत्व अब 18 है, जो 23 से कम है, इसलिए हम इस बार निचले आधे हिस्से को त्याग देते हैं।

[22, 23, 24, 50]

जो बन जाता है

[22, 23]

जो अंततः बन जाता है

[23]

कुल मिलाकर, हमें उस संख्या को खोजने के लिए ऐरे को 4 बार आधा करना पड़ा जिसे हम 16 की लंबाई वाले ऐरे में लक्षित कर रहे थे।

इसे सामान्यीकृत करने के लिए, हम कह सकते हैं कि बाइनरी सर्च के लिए सबसे खराब स्थिति ऐरे को आधा में विभाजित करने की अधिकतम संख्या के बराबर है।

गणित में, हम लॉगरिदम का उपयोग इस प्रश्न का उत्तर देने के लिए करते हैं, "इस संख्या को कितनी बार गुणा करें कि वह संख्या प्राप्त हो?" यहाँ हम अपनी समस्या पर लॉगरिदम कैसे लागू करते हैं:

इस प्रकार हम कह सकते हैं कि बाइनरी सर्च के लिए बिग-O, या सबसे खराब स्थिति का रन टाइम, log(base 2) n है।

समेटना

बिग-O नोटेशन यह कहने का एक फैंसी तरीका है, "अरे, इसके लिए सबसे खराब स्थिति क्या है?" कंप्यूटर साइंस को अलग रखते हुए, एक वास्तविक दुनिया का उदाहरण यह हो सकता है कि जब आप अपने प्लंबर से पूछते हैं कि टूटे नल को ठीक करने में कितना खर्च आएगा। वह जवाब दे सकता है, "ठीक है, मैं गारंटी दे सकता हूं कि यह $2,000 से अधिक नहीं होगा।" यह एक ऊपरी बाउंड है, हालांकि आपके लिए बहुत उपयोगी नहीं।

इसके कारण, अन्य बिग-O नोटेशन का अक्सर उपयोग किया जाता है। उदाहरण के लिए, बिग-थीटा निचली बाउंड और ऊपरी बाउंड दोनों की परवाह करता है। इस मामले में, प्लंबर जवाब देगा, "ठीक है, यह $1,000 से कम नहीं होगा लेकिन यह $2,000 से अधिक नहीं होगा।" यह कहीं अधिक उपयोगी है।

पढ़ने के लिए धन्यवाद, और मुझे आशा है कि इस पोस्ट ने बिग-O नोटेशन को कम से कम थोड़ा कम डरावना विषय बनाने में मदद की!