algorithm - Meaning of Big O notation -

हमारे शिक्षक ने हमें बिग ओ संकेतन की निम्नलिखित परिभाषा दी:

  O (f (n)): एक समारोह जी (एन) ओ (एफ (एन)) में है ("एफ (एन) का बड़ा ओफ़") अगर वहां मौजूद स्थिरांक c & gt; 0 और एन जैसे कि | जी (एन) | ≤ सी | एफ (एन) | सभी के लिए n & gt; एन।  

मैं इस परिभाषा के विभिन्न घटकों को अलग करने की कोशिश कर रहा हूं। सबसे पहले, मैं जी (एन) के लिए में O (f (n)) के लिए इसका क्या मतलब है, मैं उलझन में हूँ। में क्या मतलब है?

अगला, मैं बयान के पूरे दूसरे हिस्से से भ्रमित हूँ। ऐसा क्यों कह रहा है कि सभी के लिए जी (एन) से कम या बराबर एफ (एन) के सभी एन> एन का अर्थ बिग ओ नोटेशन के बारे में कुछ भी नहीं है?

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

सबसे पहले, मैं ओ (एफ (एन)) में रहने के लिए जी (एन) के लिए इसका क्या अर्थ है, इस बात से उलझन में हूँ। इसका मतलब क्या है?

इस निर्माण में, O (f (n)) एक फ़ंक्शन का सेट है। इस प्रकार O (N) सभी कार्यों का सेट है जो (सरल शब्दों में) एन के आनुपातिक हैं क्योंकि एन अनंतता को जाता है।

"इन" शब्द का अर्थ है ... "सेट का सदस्य है"।

ऐसा क्यों कह रहा है कि सभी के लिए जी (एन) के बराबर मूल्य या उससे कम समान एफ (एन) n> एन का अर्थ बिग ओ नोटेशन के बारे में कुछ भी नहीं है ?

यह परिभाषा है और इसके अलावा आपने अपने सारांश में c शब्द की उपेक्षा की है, और यह परिभाषा का एक महत्वपूर्ण भाग है।

मेरे सामान्य अंतर्ज्ञान के लिए क्या बिग ओ नोटेशन का मतलब है कि यह एक एल्गोरिथ्म के क्रम का वर्णन करने का एक तरीका है। उदाहरण के लिए, यदि बुलबुला प्रकार सबसे खराब स्थिति में ओ (एन ^ 2) में चलता है, तो इसका मतलब है कि एल्गोरिथम को पूरा करने के लिए यह एन ^ 2 के संचालन (इस मामले की तुलना में) का समय लेता है। मुझे नहीं पता कि यह अंतर्ज्ञान उपरोक्त परिभाषा से कैसे होता है।

आपका अंतर्ज्ञान दो मामलों में गलत है।

• सबसे पहले, असली O (N ^ 2) की परिभाषा नहीं है कि यह N ^ 2 संचालन लेता है यह है कि यह आनुपातिक N ^ 2 संचालन लेता है यही वह जगह है जहां c में आता है।

• दूसरे, यह केवल N ^ 2 के लिए आनुपातिक है N के बड़े पर्याप्त मान बिग ओ संकेतन नहीं छोटे के लिए क्या होता है N यह तब होता है जब समस्या का आकार तराजू होता है।

इसके अलावा, एक टिप्पणी टिप्पणी के रूप में "आनुपातिक" यहां सही वाक्यांश नहीं है। यह कहना सही होगा कि "आनुपातिक की ओर जाता है" ... लेकिन वास्तविकता में यहां पर जो कुछ भी हो रहा है उसका कोई सामान्य अंग्रेजी विवरण नहीं है। असली परिभाषा गणितीय है।

यदि आप अब उस परिभाषा को प्रकाश में पढ़ते हैं, तो आपको यह देखना चाहिए कि यह सिर्फ अच्छी तरह से फिट बैठता है।

---

^{ध्यान दें कि बिग ओ की परिभाषाएं और जटिलता के संबंधित उपायों को भी कैलकुलेशन शब्दावली में व्यक्त किया जा सकता है, यानी "सीमाएं" का प्रयोग करना। हालांकि, आम तौर पर हम जिस चीज के बारे में बात कर रहे हैं वह बात कर रहे हैं, यानी एक पूर्णांक संख्या निर्देश, एक पूर्णांक संख्या बाइट्स कैलकुल्स वास्तव में वास्तविक संख्याओं को शामिल करने वाले कार्यों के बारे में है। इसलिए, आप तर्क दे सकते हैं कि ऊपर की संरचना बेहतर है। ओटीओएच, एक वास्तविक गणितज्ञ शायद इस तर्क में बस-आकार वाले छेद देखेंगे।)}