बड़े-बड़े संबंधों को कैसे साबित करें

Question

अरे, शीर्षक शायद थोड़ा सा बंद है, इसलिए यदि आप इसे बेहतर तरीके से रखना चाहते हैं तो कृपया इसे सही करें।

एक होमवर्क असाइनमेंट मैं निम्नलिखित के साथ कई कार्य दिया गया है के रूप में:

Let च (एन) और जी (एन) asymptotically सकारात्मक कार्यों हो। निम्नलिखित अनुमानों में से प्रत्येक को साबित या अस्वीकार करें।

a. f(n) = O(g(n)) implies g(n) = O(f(n)) 

अब, मेरा असली सवाल यह है कि - आप इसे औपचारिक तरीके से साबित करने के बारे में कैसे जाएंगे? मुझे पता है कि उपरोक्त आसान होगा क्योंकि मैं आसानी से इसे अस्वीकार करने के लिए एक काउंटर उदाहरण प्रदान कर सकता हूं, लेकिन तर्क के लिए हम कहते हैं कि हम काउंटर उदाहरणों के बिना ऐसा करना चाहते हैं, बेशक यह कुछ अन्य उदाहरणों के साथ जारी है यह काम नहीं करेगा।

मैं थोड़ा अटक कर रहा हूँ, मैं निम्नलिखित असमानता ऊपर लिखा है (< साथ = से कम या बराबर होने)

f(n) <= c1 * g(n) 
g(n) <= c2 * f(n) 

लेकिन मैं कैसे मैं एक एकल में इन 2 inequations गठबंधन होगा की अनिश्चित हूँ (में) समीकरण और इसे अस्वीकार करें। मुझे सबसे यकीन है कि यह कुछ आसान है जिसे मैंने आसानी से अनदेखा कर दिया है और मैं इस समय बेवकूफ़ बन रहा हूं - लेकिन यह कैसे करना है इसके बारे में कोई संकेतक/ठोस उदाहरण बहुत अच्छा होगा, ताकि मैं काम करने में सक्षम होना चाहिए इन प्रश्नों में से बाकी मेरे बारे में बताएं।

Answer 1

आप counterexample का उपयोग किए बिना इसे क्यों अस्वीकार करना चाहते हैं? दावे को अस्वीकार करने का यह सबसे सीधा तरीका है।

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

इस मामले में, आप f(n) <= c1 * g(n) से सच होने के साथ शुरू करते हैं, क्योंकि इसका मतलब f(n) = O(g(n)) है। अब आप यह मानना ​​चाहते हैं कि g(n) <= c2 * f(n) सभी f और g के लिए सच है (यह अंतिम भाग बहुत महत्वपूर्ण है, क्योंकि आप निश्चित रूप से f और g चुन सकते हैं जैसे कि यह सत्य है), और दिखाएं कि यह क्यों काम नहीं कर सकता है। आपके लिए मेरा संकेत: f और g चुनें जैसे कि यह काम नहीं कर सकता है, और यह दिखाता है कि यह c1 और c2 की अपनी पसंद से काम नहीं कर सकता है।

Answer 2

कुछ संकेत:
मत भूलना कि f(n) = O(g(n)) एक set notation है और आप असमानताओं के एक गणितीय फार्म के लिए यह बदल सकते हैं।

सरल आपरेशनों आप हे -notation के साथ क्या कर सकते हैं:,

• f(n) = O(f(n))
• c * O(f(n)) = O(f(n)) अगर ग स्थिर है
• O(f(n)) + O(f(n)) = O(f(n))
• O(O(f(n))) = O(f(n))
• O(f(n)) * O(g(n)) = O(f(n)g(n))
• O(f(n)g(n)) = f(n) * O(g(n))

(कम्प्यूटर की कला प्रोग्रामिंग, खंड 1 - हे -Notation)