algorithm - बड़ा Ө नोटेशन वास्तव में क्या प्रतिनिधित्व करता है?




computer-science big-o (3)

मैं बड़े ओ, बड़े ओमेगा, और बड़े थेटा नोटेशन के बीच मतभेदों के बारे में वास्तव में उलझन में हूं।

मैं समझता हूं कि बड़ा ओ ऊपरी बाउंड है और बड़ा ओमेगा निचला बाध्य है, लेकिन बड़ा Ө (थेटा) वास्तव में क्या करता है?

मैंने पढ़ा है कि इसका मतलब तंग बंधन है , लेकिन इसका क्या अर्थ है?


आपको जवाब देने के लिए, एसिम्प्टोटिक नोटेशन और एसिम्प्टोटिक नोटेशन में फ़ंक्शन को भी समझाया जाना चाहिए। यदि आपके पास इसे पढ़ने के लिए धैर्य है, तो अंत में चीजें बहुत स्पष्ट होंगी।

1. Asymptotic नोटेशन

एल्गोरिदम के बारे में सोचने के लिए आप 2 मुख्य विचारों का उपयोग कर सकते हैं:

  1. निर्धारित करें कि एल्गोरिदम अपने इनपुट के संदर्भ में कितना समय लेता है।
  2. फ़ोकस करें कि इनपुट आकार के साथ कोई फ़ंक्शन कितना तेज़ हो जाता है; चलने वाले समय की वृद्धि की उर्फ ​​दर। उदाहरण: मान लीजिए कि आकार ए के इनपुट पर चलने वाला एल्गोरिदम 6 एन ^ 2 + 100 एन + 300 मशीन निर्देश लेता है। 6 एन ^ 2 शब्द शेष शर्तों की तुलना में बड़ा हो जाता है, 100 एन + 300, एक बार एन पर्याप्त बड़ा हो जाता है, 20 इस मामले में।

हम कहेंगे कि इस एल्गोरिदम का चलने का समय एन ^ 2 के रूप में बढ़ता है, गुणांक 6 और शेष शर्तों को 100 एन + 300 छोड़ देता है। इससे कोई फर्क नहीं पड़ता कि हम किस गुणांक का उपयोग करते हैं; जब तक चलने का समय एन ^ 2 + बी एन + सी होता है, कुछ संख्याओं के लिए> 0, बी, और सी, हमेशा एन का मान होगा जिसके लिए n ^ 2 बी एन + सी से अधिक है , और एन बढ़ने के रूप में यह अंतर बढ़ता है। निरंतर गुणांक और कम महत्वपूर्ण शर्तों को छोड़कर, हम एसिम्प्टोटिक नोटेशन का उपयोग करते हैं।

2. बिग-थेटा

यहां रैखिक खोज का एक सरल कार्यान्वयन है

var doLinearSearch = function(array) {
  for (var guess = 0; guess < array.length; guess++) {
    if (array[guess] === targetValue) { 
        return guess;  // found it!
    }
  }
  return -1;  // didn't find it
};
  • इन छोटी गणनाओं में से प्रत्येक प्रत्येक बार निष्पादित होने पर निरंतर समय लेता है। यदि फॉर-लूप एन बार पुनरावृत्त करता है, तो सभी एन पुनरावृत्तियों के लिए समय c1 * n है, जहां सी 1 एक लूप पुनरावृत्ति में गणना के लिए समय का योग है। फॉर-लूप (0 को अनुमान लगाना सहित) और संभवतः अंत में -1 लौटने के लिए इस कोड में अतिरिक्त ओवरहेड है। आइए इस ओवरहेड सी 2 के लिए समय कॉल करें, जो स्थिर भी है। इसलिए, सबसे खराब मामले में रैखिक खोज के लिए कुल समय सी 1 * एन + सी 2 है।
  • निरंतर कारक सी 1 और निम्न-आदेश अवधि सी 2 हमें चलने वाले समय के विकास की दर के बारे में नहीं बताता है। महत्वपूर्ण बात यह है कि रैखिक खोज का सबसे खराब मामला चलने का समय सरणी आकार एन की तरह बढ़ता है। इस चलने वाले समय के लिए हम जिस नोटेशन का उपयोग करते हैं वह Θ (एन) है। यह यूनानी पत्र "थेटा" है, और हम कहते हैं, "बड़े-थेटा ऑफ एन" या सिर्फ "थेटा ऑफ एन"।
  • जब हम कहते हैं कि एक विशेष चलने का समय Θ (एन) है, तो हम कह रहे हैं कि एक बार एन पर्याप्त हो जाता है, चलने का समय कम से कम 1 * एन होता है और कुछ के लिए अधिकांश के 2 * n स्थिरांक के 1 और के 2। Θ (एन) के बारे में सोचने का तरीका यहां दिया गया है

  • एन के छोटे मूल्यों के लिए, हमें परवाह नहीं है कि चलने का समय k 1 * n या k 2 * n के साथ तुलना करता है। लेकिन एक बार एन धराशायी रेखा के दाहिनी तरफ या पर्याप्त हो जाता है-चलने का समय के 1 * एन और के 2 * एन के बीच सैंडविच होना चाहिए। जब तक ये स्थिरांक के 1 और के 2 मौजूद होते हैं, हम कहते हैं कि चलने का समय Θ (एन) है।

  • जब हम बड़े-Θ नोटेशन का उपयोग करते हैं, तो हम कह रहे हैं कि हमारे पास चलने वाले समय पर एक असीम रूप से तंग है । "असम्बद्ध रूप से" क्योंकि यह केवल एन के बड़े मूल्यों के लिए महत्वपूर्ण है। "तंग बाध्य" क्योंकि हमने चलने का समय ऊपर और नीचे एक निरंतर कारक के भीतर खींचा है।

3. एसिम्प्टोटिक नोटेशन में कार्य

  • मान लीजिए कि इनपुट आकार के बावजूद एक एल्गोरिदम ने निरंतर समय लिया। उदाहरण के लिए, यदि आपको एक सरणी दी गई है जो पहले से ही बढ़ते क्रम में क्रमबद्ध है और आपको न्यूनतम तत्व मिलना है, तो इसमें निरंतर समय लगेगा, क्योंकि न्यूनतम तत्व सूचकांक 0 पर होना चाहिए क्योंकि हम n के फ़ंक्शन का उपयोग करना पसंद करते हैं एसिम्प्टोटिक नोटेशन में, आप कह सकते हैं कि यह एल्गोरिदम Θ (एन ^ 0) समय में चलता है। क्यूं कर? क्योंकि n ^ 0 = 1, और एल्गोरिदम का चलने का समय 1 के कुछ स्थिर कारक के भीतर होता है। प्रैक्टिस में, हम Θ (n ^ 0) नहीं लिखते हैं, हालांकि; हम लिखते हैं Θ (1)
  • यहां एसिम्प्टोटिक नोटेशन में फ़ंक्शंस की एक सूची दी गई है जिसे हम अक्सर एल्गोरिदम का विश्लेषण करते समय सामना करते हैं, जो धीमे से तेज़ी से बढ़ते हुए सूचीबद्ध होते हैं। यह सूची व्यापक नहीं है; ऐसे कई एल्गोरिदम हैं जिनके चलने वाले समय यहां प्रकट नहीं होते हैं:
  • Θ (1) (उर्फ निरंतर खोज)
  • Θ (एलजी एन) (उर्फ बाइनरी खोज)
  • Θ (एन) (उर्फ रैखिक खोज)
  • Θ (एन * एलजी एन)
  • Θ (n ^ 2)
  • Θ (एन ^ 2 * एलजी एन)
  • Θ (n ^ 3)
  • Θ (2 ^ n)

  • ध्यान दें कि एक घातीय कार्य एक ^ एन, जहां ए> 1, किसी भी बहुपद कार्य n ^ b से तेज़ी से बढ़ता है, जहां बी कोई स्थिर है।

4. बिग-ओ नोटेशन

  • हम ऊपर-नीचे निरंतर कारकों के भीतर एक चलने वाले समय के विकास को असम्बद्ध रूप से बाध्य करने के लिए बड़े-Θ नोटेशन का उपयोग करते हैं। कभी-कभी हम केवल ऊपर से बंधना चाहते हैं। एसिम्प्टोटिक नोटेशन का एक रूप होना सुविधाजनक होगा जिसका अर्थ है "चलने का समय सबसे अधिक बढ़ता है, लेकिन यह धीरे-धीरे बढ़ सकता है।" हम इस तरह के अवसरों के लिए "बड़े-ओ" नोटेशन का उपयोग करते हैं।
  • यदि एक चलने का समय ओ (एफ (एन)) है, तो बड़े पर्याप्त एन के लिए, कुछ स्थिर के लिए चलने का समय अधिकांश के * एफ (एन) पर होता है। यहां चलने वाले समय के बारे में सोचना है कि ओ (एफ (एन)) है:
  • यदि आप बड़े-Θ नोटेशन की परिभाषा पर वापस जाते हैं, तो आप देखेंगे कि यह बड़े-ओ नोटेशन की तरह दिखता है, सिवाय इसके कि बड़े-Θ नोटेशन ऊपर से नीचे की बजाय ऊपर और नीचे दोनों से चल रहे हैं। अगर हम कहते हैं कि एक चलती समय Θ (एफ (एन)) किसी विशेष स्थिति में है, तो यह भी ओ (एफ (एन)) है। उदाहरण के लिए, हम कह सकते हैं कि बाइनरी खोज का सबसे खराब मामला चलने का समय Θ (एलजी एन) है, यह ओ (एलजी एन) भी है। बातचीत आवश्यक नहीं है: जैसा कि हमने देखा है, हम कह सकते हैं कि बाइनरी खोज हमेशा ओ (एलजी एन) समय में चलती है लेकिन यह नहीं कि यह हमेशा Θ (एलजी एन) समय में चलता है।
  • मान लें कि आपके पास अपनी जेब में 10 डॉलर हैं। आप अपने दोस्त के पास जाते हैं और कहते हैं, "मेरे पास मेरी जेब में बहुत पैसा है, और मैं गारंटी देता हूं कि यह दस लाख डॉलर से अधिक नहीं है।" आपका कथन बिल्कुल सही है, हालांकि बहुत सटीक नहीं है। एक मिलियन डॉलर 10 डॉलर पर ऊपरी बाउंड है, जैसे ओ (एन) द्विआधारी खोज के चलने वाले समय पर ऊपरी बाध्य है।
  • अन्य, बाइनरी खोज पर अपर्याप्त, ऊपरी सीमाएं ओ (एन ^ 2), ओ (एन ^ 3), और ओ (2 ^ एन) होगी। लेकिन किसी भी मामले में बाइनरी खोज के चलने के समय का वर्णन करने के लिए Θ (एन), Θ (एन ^ 2), Θ (एन ^ 3), औरΘ (2 ^ एन) में से कोई भी सही नहीं होगा।

5. बिग-Ω (बिग-ओमेगा) नोटेशन

  • कभी-कभी, हम यह कहना चाहते हैं कि एक एल्गोरिदम ऊपरी बाउंड प्रदान किए बिना कम से कम एक निश्चित समय लेता है। हम बड़े-Ω नोटेशन का उपयोग करते हैं; वह यूनानी पत्र "ओमेगा" है।
  • यदि एक चलने का समय Ω (एफ (एन)) है, तो पर्याप्त पर्याप्त एन के लिए, कुछ स्थिर के लिए चलने का समय कम से कम के * एफ (एन) होता है। यहां चलने वाले समय के बारे में सोचना है कि Ω (एफ (एन)) है:
  • हम कहते हैं कि चलने का समय "एफ (एन) का बड़ा-Ω है।" हम एसिम्प्टोटिक निचली सीमाओं के लिए बड़े-Ω नोटेशन का उपयोग करते हैं, क्योंकि यह बड़े पर्याप्त इनपुट आकारों के लिए नीचे से चलने वाले समय के विकास को सीमित करता है।
  • जैसे Θ (एफ (एन)) स्वचालित रूप से ओ (एफ (एन)) का तात्पर्य है, यह स्वचालित रूप से Ω (एफ (एन)) का तात्पर्य है। तो हम कह सकते हैं कि बाइनरी खोज का सबसे खराब मामला चलने का समय Ω (एलजी एन) है। हम बड़े-Ω नोटेशन का उपयोग करके सही, लेकिन अपरिवर्तनीय, कथन भी कर सकते हैं। उदाहरण के लिए, जैसे कि आपके पास वास्तव में आपकी जेब में दस लाख डॉलर हैं, आप सचमुच कह सकते हैं "मेरे पास मेरी जेब में बहुत पैसा है, और यह कम से कम 10 डॉलर है," आप यह भी कह सकते हैं कि सबसे खराब केस चल रहा है बाइनरी खोज का समय Ω (1) है, क्योंकि इसमें कम से कम स्थिर समय लगता है।

संदर्भ: https://www.khanacademy.org


इसका मतलब है कि दिए गए फ़ंक्शन में एल्गोरिदम बड़ा-ओ और बड़ा-ओमेगा दोनों है।

उदाहरण के लिए, यदि यह Ө(n) , तो कुछ स्थिर k , जैसे कि आपका फ़ंक्शन (रन-टाइम, जो कुछ भी) पर्याप्त रूप से बड़े n लिए n*k से बड़ा है, और कुछ अन्य निरंतर K जैसे आपका कार्य पर्याप्त रूप से बड़े n लिए n*K से छोटा है।

दूसरे शब्दों में, पर्याप्त रूप से बड़े n , यह दो रैखिक कार्यों के बीच सैंडविच है:

के k < K और n पर्याप्त रूप से बड़े, n*k < f(n) < n*K


थेटा (एन): एक फंक्शन f(n) Theta(g(n)) , यदि सकारात्मक स्थिरांक c1 और c2 मौजूद है जैसे कि f(n) c1(g(n)) और c2(g(n)) c1(g(n)) बीच सैंडविच किया जा सकता है c2(g(n)) । यानी यह ऊपरी और साथ ही कम बाध्य दोनों देता है।

थेटा (जी (एन)) = {एफ (एन): सकारात्मक स्थिरांक सी 1, सी 2 और एन 1 मौजूद है जैसे 0 <= सी 1 (जी (एन)) <= एफ (एन) <= ​​सी 2 (जी (एन)) सभी एन> = एन 1} के लिए

जब हम कहते हैं कि f(n)=c2(g(n)) या f(n)=c1(g(n)) यह असम्बद्ध रूप से तंग बाध्यता का प्रतिनिधित्व करता है।

ओ (एन): यह केवल ऊपरी बाउंड देता है (हो सकता है या तंग नहीं हो सकता है)

ओ (जी (एन)) = {एफ (एन): सकारात्मक स्थिरांक सी और एन 1 मौजूद है जैसे कि 0 <= f (n) <= cg (n) सभी n> = n1}

पूर्व : बाध्य 2*(n^2) = O(n^2) असम्बद्ध रूप से तंग है, जबकि बाध्य 2*n = O(n^2) असम्बद्ध रूप से तंग नहीं है।

ओ (एन): यह केवल ऊपरी बाउंड देता है (कभी भी तंग बंधे नहीं)

ओ (एन) और ओ (एन) के बीच उल्लेखनीय अंतर एफ (एन) सभी n> = n1 के लिए सीजी (एन) से कम है लेकिन ओ (एन) के बराबर नहीं है।

पूर्व : 2*n = o(n^2) , लेकिन 2*(n^2) != o(n^2)





big-theta