रूबी के साथ बिग-ओ नोटेशन की खोज

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

रैखिक खोज के लिए बिग-ओ ढूँढना

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

रूबी में एक कार्यान्वयन यहां दिया गया है।

def find_number_via_linear_search(array, target)
  counter = 0 

  # iterate through the given array starting 
  # at index 0 and continuing until the end 
  while counter < array.length 
    if array[counter] == target 
      # exit if target element found 
      return "linear search took: #{counter} iterations" 
    else 
      counter += 1 
    end 
  end 

  return "#{target} not found" 
end 

हम इस विधि को इस तरह से घुमा सकते हैं:

# Let's create an array with 50 integers
# and then re-arrange the order to make
# things more interesting
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"

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

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

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

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

आइए आगे द्विआधारी खोज पर विचार करें। यहां बताया गया है कि आप पूर्व-क्रमबद्ध . की बाइनरी खोज कैसे करते हैं सरणी:1। मध्य तत्व लें
2. यदि element == target हम कर रहे हैं3. अगर element > target सरणी के शीर्ष आधे भाग को छोड़ दें। यदि element < target सरणी 5 के निचले आधे हिस्से को छोड़ दें। चरण 1 पर शेष सरणी के साथ प्रारंभ करें

नोट:यदि आप रूबीस्ट हैं, तो एक अंतर्निहित बी-सर्च विधि है जो आपके लिए इस एल्गोरिदम को लागू करती है!

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

लेकिन मेरा अनुमान है, शब्दकोश के बीच में "पी" नहीं होगा, इसलिए शायद हमें "लामा" शब्द मिल जाएगा। "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 थी।

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

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

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

रैपिंग अप

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

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

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