साबित करें = बिग-ओ (1) प्रेरण

Question

का उपयोग करके मुझे पता है कि संबंध n = Big-O (1) गलत है। लेकिन अगर हम बिग-ओ से जुड़े प्रेरण का उपयोग करते हैं तो इसे साबित किया जा सकता है। लेकिन झूठ यह है कि हम बिग-ओ शामिल नहीं कर सकते हैं। लेकिन मेरा सवाल यह है कि कैसे हम स्थिरांक का उपयोग करके संबंध को अस्वीकार कर सकते हैं।

झूठा प्रमाण यहां है, कृपया मुझे स्थिरांक का उपयोग करके झूठा होने का सबूत दें। मैं स्थिरांक के साथ भ्रमित हो रहा हूं, मुझे नहीं पता कि सबूत में इस्तेमाल किए गए प्रत्येक संबंध में अलग-अलग स्थिरता या समान है। कृपया विषय पर प्रबुद्ध करें।

TO prove: n= O(1) 
for n=1 , 1= O(1) proved 

प्रेरण परिकल्पना: चलो यह सच है: एन-1 = हे (1) अब हम साबित होता है कि एन = हे (1)

LHS : n = (n-1) + 1 
     = O(1) + 1 
     = O(1) + O(1) 
     = O(1) 

झूठी साबित कर दिया .. मैं स्पष्टीकरण चाहते हैं < = और स्थिरांक के मामले में गिरावट का, जो बिग-ओ की मूल परिभाषा में है।

Answer 1

एक बात आपको यहां समझनी है कि बिग-ओ या बस ओ 'दर' को दर्शाता है जिस पर एक कार्य बढ़ता है। आप इस विशेष संपत्ति को साबित करने के लिए गणितीय प्रेरण का उपयोग नहीं कर सकते हैं।

एक उदाहरण

O(n^2) = O(n^2) + O(n) 

सरल गणित से है, ऊपर बयान हे (एन) = 0 जो नहीं है निकलता है। तो मैं कहूंगा कि इसके लिए एमआई का उपयोग न करें। एमआई पूर्ण मूल्यों के लिए अधिक उपयुक्त है।

Answer 2

बड़ा ओ नोटेशन कार्यों के बारे में है, इसलिए 1 = O(1) जैसे बयान का कोई अर्थ नहीं है। आप यहां जो साबित कर रहे हैं वह यह है कि यदि आप n और निरंतर कार्य f(x) = n पर f = O(1) को सत्य मानते हैं और कोई विरोधाभास नहीं देते हैं। सबूत के साथ कोई समस्या नहीं है, समस्या यह है कि आप फंक्शन f(n) = n के साथ निरंतर फ़ंक्शन f(x) = n को भ्रमित कर रहे हैं। बाद के लिए हमारे पास f = O(n) है और यदि आप इसे अपनी विधि से साबित करने का प्रयास करते हैं तो आप देखेंगे कि यह काम नहीं करेगा।

Answer 3

वहाँ एक बहुत बड़ा तार्किक भ्रम यहां छिपा हुआ है: (1) कार्यों का एक सेट है

 
LHS : n = (n-1) + 1 
     = O(1) + 1 
     = O(1) + O(1) 
     = O(1) 

n एक समारोह और और ऑमिक्रॉन है। न तो एक संख्या है (और प्रेरण प्रमाण सभी व्यक्तिगत संख्याओं के पूरे समूह के लिए चीजों को साबित करने के बारे में हैं, एक में गिरावट आई है)। बराबर संकेतों का उपयोग, जैसे एन = और ओमिक्रॉन; (1), is an informal shorthand for f ∈ Ο(1), where f(x) = x।

यह सबूत दो में the fallacy of equivocation तरीके का उपयोग करता है: बल्कि एक पूरे समारोह

से

• कि n है एक नंबर (आगमनात्मक यात्रा में अगला नंबर) का बहाना बनाकर बहाना बनाकर बराबर संकेत है कि इसका मतलब यह दो संख्या बराबर होती है, जिसका मतलब है कि

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

बेस मामला:

 
let h(x) = 1 in 
      h ∈ Ο(1)  [Any function is in Ο(that function)] 

प्रेरक मामला:

 
      n = (n - 1) + 1 [Algebraic identity] 
     n - 1 = n - 1  [Arithmetic] 

let f(x) = x 
    g(x) = f(x) - 1 in 
      g ∈ Ο(1)  [Assume g ∈ Ο(1) because a different function, h, was] 
      f ∈ Ο(1 + 1) [By definition of Ο] 
      f ∈ Ο(2)  [Arithmetic] 

यह बहुत स्पष्ट है कि यह एक प्रेरण सबूत बिल्कुल नहीं है हो जाता है। यह अपने अधिकार में भी एक वैध सबूत नहीं है, क्योंकि हमने केवल साबित किया है कि एच ∈ और ओमिक्रॉन; (1), जिसका जी ∈ और ओमिक्रॉन; (1) के साथ कुछ भी नहीं है, क्योंकि ये कार्य एक-दूसरे से बहुत अलग हैं ।

Answer 4

यदि आपको बिग-ओ नोटेशन से जुड़े किसी भी कठोर सबूत की आवश्यकता है, तो आपको format definition of Big-O से शुरू करने की आवश्यकता है, इस सबूत में आप केवल O(1) + 1 = O(1) नहीं कह सकते हैं। आपको औपचारिक परिभाषा के संदर्भ में सबूत करने की आवश्यकता है। यह साबित करने के लिए कि एक फ़ंक्शन (उदाहरण के लिए f(n) = n) ओ (1) है, आपको परिभाषा से मेल खाने वाले अद्वितीय x0 और M को खोजने की आवश्यकता है। आप प्रेरण के माध्यम से इस प्रदर्शन कर सकते हैं, और आप भी परिभाषा का उपयोग दिखाने के लिए कि f(n) = n नहीं है विरोधाभास द्वारा एक सबूत कर सकते हैं O(1)

बस के रूप में Olathe अपने जवाब में कहा गया है, तो आप सिर्फ बड़े-ओ सेट नहीं जोड़ सकते हैं और कार्यों। किसी विशेष बिग-ओ सेट के सदस्य के रूप में फ़ंक्शन को वर्गीकृत करने की औपचारिक परिभाषा से प्रारंभ करें।