बड़ा ओ

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

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

यदि आप बिग ओ के संदर्भ में कोड का मूल्यांकन करने में सक्षम हैं, तो आपको "स्मार्ट लड़का" माना जाता है। और सबसे अधिक संभावना है कि आप अपने अगले साक्षात्कार से गुजरेंगे। आपको इस सवाल से नहीं रोका जाएगा कि क्या n ^ 2 के विरुद्ध n लॉग एन कोड के किसी भी टुकड़े की जटिलता को कम करना संभव है।

डेटा संरचनाएं

डेटा संरचना की पसंद विशिष्ट कार्य पर निर्भर करती है: डेटा के प्रकार और उनके प्रसंस्करण के लिए एल्गोरिथ्म पर। कुछ प्रकार के एल्गोरिदम के लिए विभिन्न प्रकार की डेटा संरचनाएं (.NET या जावा या एलिक्सिर में) बनाई गई थीं।

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

यहां हम केवल संख्याओं के सरणियों का उपयोग करेंगे (जैसे एक साक्षात्कार में)। जावास्क्रिप्ट उदाहरण।

आइए सबसे सरल से शुरुआत करें: O (1)

5 नंबर की एक सरणी लें:

const nums = [1,2,3,4,5]; 

मान लें कि आपको पहला तत्व प्राप्त करने की आवश्यकता है। हम इसके लिए सूचकांक का उपयोग करते हैं:

 const nums = [1,2,3,4,5]; const firstNumber = nums[0]; 

यह एल्गोरिथ्म कितना जटिल है? हम कह सकते हैं: "सभी जटिल नहीं - बस सरणी का पहला तत्व लें।" यह सच है, लेकिन इनपुट (इनपुट ऑपरेशंस ) के आधार पर, परिणाम प्राप्त करने के लिए किए गए संचालन की संख्या के माध्यम से जटिलता का वर्णन करना अधिक सही है।

दूसरे शब्दों में: इनपुट मापदंडों की संख्या बढ़ने पर कितने ऑपरेशन बढ़ेंगे।

हमारे उदाहरण में, 5 इनपुट पैरामीटर हैं, क्योंकि सरणी में 5 तत्व हैं। परिणाम प्राप्त करने के लिए, आपको एक ऑपरेशन (सूचकांक द्वारा एक तत्व लेना) करने की आवश्यकता है। यदि सरणी में 100 तत्व हैं, तो कितने ऑपरेशनों की आवश्यकता होगी? या 1000? या 100,000? सभी समान, केवल एक ऑपरेशन की आवश्यकता है।

वह है: "सभी संभावित इनपुट डेटा के लिए एक ऑपरेशन" - ओ (1)।

O (1) को "ऑर्डर 1 जटिलता" (ऑर्डर 1) के रूप में पढ़ा जा सकता है, या "एल्गोरिथ्म निरंतर / निरंतर समय में चलता है" (निरंतर)।

आपने पहले ही अनुमान लगा लिया था कि O (1) एल्गोरिदम सबसे कुशल हैं।

परिवर्तन और "आदेश n का समय": O (n)

अब आइए सरणी के तत्वों का योग खोजें:

 const nums = [1,2,3,4,5]; let sum = 0; for(let num of nums){ sum += num; } 

फिर हम खुद से पूछते हैं: हमें कितने इनपुट ऑपरेशन की आवश्यकता है? यहां आपको सभी तत्वों के माध्यम से सॉर्ट करने की आवश्यकता है, अर्थात्। प्रत्येक तत्व पर ऑपरेशन। सरणी जितनी बड़ी होगी, उतने ही अधिक ऑपरेशन होंगे।

बिग ओ नोटेशन का उपयोग करना: O (n), या "ऑर्डर n (ऑर्डर n) की जटिलता"। इसके अलावा, इस प्रकार के एल्गोरिथ्म को "रैखिक" कहा जाता है या यह कि एल्गोरिथ्म "रैखिक रूप से छोटा" है।

के विश्लेषण

क्या हम योग को अधिक कुशल बना सकते हैं? आम तौर पर नहीं। और अगर हम जानते हैं कि सरणी को 1 पर शुरू करने की गारंटी है, तो सॉर्ट किया गया है और कोई अंतराल नहीं है? तब हम सूत्र S = n (n + 1) / 2 (जहाँ n सरणी का अंतिम तत्व है) लागू कर सकते हैं:

 const sumContiguousArray = function(ary){ //get the last item const lastItem = ary[ary.length - 1]; //Gauss's trick return lastItem * (lastItem + 1) / 2; } const nums = [1,2,3,4,5]; const sumOfArray = sumContiguousArray(nums); 

ऐसा एल्गोरिथ्म O (n) की तुलना में बहुत अधिक कुशल है, इसके अलावा, इसे "निरंतर / निरंतर समय" में निष्पादित किया जाता है, अर्थात यह ओ (1) है।

वास्तव में, एक से अधिक ऑपरेशन हैं: आपको सरणी की लंबाई प्राप्त करने, अंतिम तत्व प्राप्त करने, गुणन और विभाजन करने की आवश्यकता है। ओ (3) या कुछ और नहीं है? बिग ओ नोटेशन में, चरणों की वास्तविक संख्या महत्वपूर्ण नहीं है, यह महत्वपूर्ण है कि एल्गोरिथ्म निरंतर समय में चलता है।

लगातार समय के एल्गोरिदम हमेशा ओ (1) होते हैं। रैखिक एल्गोरिदम के साथ भी, वास्तव में, संचालन ओ (एन + 5) हो सकता है, बिग ओ में अंकन ओ (एन) है।

सर्वोत्तम समाधान नहीं: O (n ^ 2)

आइए एक फ़ंक्शन लिखें जो डुप्लिकेट के लिए सरणी की जांच करता है। नेस्टेड लूप सॉल्यूशन:

 const hasDuplicates = function (num) { //loop the list, our O(n) op for (let i = 0; i < nums.length; i++) { const thisNum = nums[i]; //loop the list again, the O(n^2) op for (let j = 0; j < nums.length; j++) { //make sure we're not checking same number if (j !== i) { const otherNum = nums[j]; //if there's an equal value, return if (otherNum === thisNum) return true; } } } //if we're here, no dups return false; } const nums = [1, 2, 3, 4, 5, 5]; hasDuplicates(nums);//true 

हम पहले से ही जानते हैं कि सरणी पुनरावृत्ति हे (n)। हमारे पास एक नेस्टेड लूप है, प्रत्येक तत्व के लिए हम फिर से पुनरावृति करते हैं - अर्थात। ओ (एन ^ 2) या "ऑर्डर एन स्क्वायर की जटिलता।"

समान संग्रह पर नेस्टेड लूप वाले एल्गोरिदम हमेशा ओ (एन ^ 2) होते हैं।

"लॉग एन के आदेश की जटिलता": ओ (लॉग एन)

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

यहाँ, एक नेस्टेड लूप का उपयोग किसी एरे में दिए गए तत्व को खोजने के लिए किया जाता है। एक सरणी में एक तत्व की खोज, कुछ शर्तों के तहत, अनुकूलित किया जा सकता है - रैखिक ओ (एन) से बेहतर किया।

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



यह एल्गोरिथ्म एक लघुगणक पर आधारित है।

लघुगणकों का त्वरित अवलोकन

एक उदाहरण पर विचार करें, x किसके बराबर होगा?

x ^ 3 = 8

हमें 8 की घनमूल लेने की आवश्यकता है - यह 2 होगा। अब और अधिक कठिन है

2 ^ x = 512

लघुगणक का उपयोग करते हुए, समस्या को लिखा जा सकता है

log2 (512) = x

"512 का आधार 2 लघुगणक x है।" "बेस 2" पर ध्यान दें, अर्थात् हम दोहों में सोचते हैं - 512 प्राप्त करने के लिए आपको कितनी बार 2 को गुणा करना होगा।

बाइनरी सर्च एल्गोरिथ्म में, प्रत्येक चरण में हम एरे को दो भागों में विभाजित करते हैं।

मेरा जोड़। यानी सबसे खराब स्थिति में, हम उतने ऑपरेशन करते हैं जितना कि हम एरे को दो भागों में विभाजित कर सकते हैं। उदाहरण के लिए, हम 4 तत्वों की एक सरणी को दो भागों में कितनी बार विभाजित कर सकते हैं? 2 बार। और 8 तत्वों की एक सरणी? 3 बार। यानी डिवीजनों / संचालन की संख्या = log2 (n) (जहां n सरणी में तत्वों की संख्या है)।

यह पता चला है कि इनपुट तत्वों की संख्या पर संचालन की निर्भरता को लॉग 2 (एन) के रूप में वर्णित किया गया है।


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

O में सुधार करें (n ^ 2) से O (n log n)

आइए डुप्लिकेट के लिए सरणी की जांच के कार्य पर लौटते हैं। हमने सरणी के सभी तत्वों पर पुनरावृत्त किया, और प्रत्येक तत्व के लिए हमने फिर से पुनरावृत्त किया। उन्होंने O (n) O (n) के अंदर किया, अर्थात O (n * n) या O (n ^ 2)।

हम नेस्टेड लूप को बाइनरी सर्च * से बदल सकते हैं। यानी हमें बस O (n) के सभी तत्वों से गुजरना होगा, अंदर हम O (लॉग एन) करते हैं। यह O (n * log n), या O (n लॉग एन) निकलता है।

 const nums = [1, 2, 3, 4, 5]; const searchFor = function (items, num) { //use binary search! //if found, return the number. Otherwise... //return null. We'll do this in a later chapter. } const hasDuplicates = function (nums) { for (let num of nums) { //let's go through the list again and have a look //at all the other numbers so we can compare if (searchFor(nums, num)) { return true; } } //only arrive here if there are no dups return false; } 

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

बिग ओ के संदर्भ में सोच रहे हैं

• संग्रह वस्तु प्राप्त करना हे (1) है। चाहे वह किसी सरणी में अनुक्रमणिका द्वारा प्राप्त कर रहा हो, या बिग ओ संकेतन में एक शब्दकोश में कुंजी द्वारा, यह ओ (1) होगा
• एक संग्रह से अधिक ऊ (n) है
• एक ही संग्रह में नेस्टेड लूप्स हे (n ^ 2)
• बांटो और जीतो हमेशा ओ (लॉग एन)
• विभाजन और जीत का उपयोग करने वाले परिवर्तन ओ हैं (एन लॉग एन)