निवेशन तरह एल्गोरिथ्म का चलने का समय सबसे ओ (n²) पर है
यह सही है?
मैंने नेट की कोशिश की लेकिन एक अच्छा स्पष्टीकरण नहीं मिला।
मुझे पता है कि किसी भी रेखीय कार्य a⋅n + बी हे (एन) और यह भी है ओ (n²):
मैं एक और सवाल है। क्या यह ओ (एन³) भी है?
T(n): अल्गो ए के चलने का समयहम सिर्फ के बारे में ऊपरी बाध्य देखभाल और T(n) बयान के लिए बाध्य लोअर: T(n) >= O(n^2)
ऊपरी बाध्य: मान लीजिए f(n) = O(n^2), तो बयान:: क्योंकि T(n) >= O(n^2), तो बाध्य T(n) लोअर की ऊपरी सीमा के बारे में कोई जानकारी नहीं है T(n) >= f(n), लेकिन f(n) कुछ भी है कि कि "छोटे" n^2 से, पूर्व हो सकता है: constant, n,..., तो वहाँ कम T(n) के लिए बाध्य के बारे में कोई निष्कर्ष है भी
=> बयान व्यर्थ है
+1 यह सही उत्तर है। – chepner
एक कारण यह हो सकता है कि ऊपरी बाउंड के बिना निचली बाउंड बहुत उपयोगी नहीं है। "कम से कम" का मतलब है कि यह एक सामान्य मामले में घातीय हो सकता है। यदि आप ऊपरी बाउंड को नहीं जानते हैं तो संभवतः आप वास्तविक एप्लिकेशन में एल्गोरिदम का उपयोग नहीं कर सकते हैं क्योंकि आप नहीं जानते कि प्रोग्राम ब्रह्मांड से पहले खत्म होता है या नहीं।
बिग ओ नोटेशन जब सही ढंग से उपयोग किया जाता है तो ऊपरी बाउंड को इंगित करता है। तो बड़े ओ के रूप में निचली बाध्य बताते हुए नोटेशन का दुरुपयोग कर रहा है।
ने कहा कि "अर्थहीन" एक मजबूत शब्द है। यह निश्चित रूप से उपयोगी जानकारी है भले ही यह पर्याप्त न हो। आपके प्रश्न के कुछ और संदर्भ के साथ आप बेहतर सहायता प्राप्त कर सकते हैं।
आपके सटीक उत्तर के लिए धन्यवाद। अगर मैं ए को सम्मिलन क्रम एल्गोरिदम के रूप में मानता हूं, तो क्या यह कहना उपयोगी है कि "इस संदर्भ में एल्गोरिदम ए का चलने का समय कम से कम ओ (एन 2) है?" – tanmoy
एक और संदेह: कोई रैखिक कार्य ए + बी ओ (एन) है और ओ (एन^2) भी है। क्या यह ओ (एन^3) भी है? – tanmoy
जैसा कि मैंने कहा, निष्पादन समय की निचली सीमा को बताने के लिए यह सही और सार्थक है, यह केवल इतना है कि इसके लिए बड़े ओ नोटेशन का उपयोग करना असामान्य है, जो आमतौर पर समय की जटिलता के ऊपरी सीमा के लिए आरक्षित होता है। यह कहकर "यह कम से कम n2 है" को अधिक औपचारिक रूप से वर्णित किया गया है (बड़ा) ओमेगा (एन^2), जिसका अर्थ है "एन^2 एसिम्प्टोटिक रूप से नीचे बाध्य"। तो आपको "ओ (..)" का उपयोग नहीं करना चाहिए जबतक कि आप "ऊपर से बंधे हुए, asymptotycally" का मतलब नहीं है। http://en.wikipedia.org/wiki/Big_O_notation –
"एल्गोरिथ्म एक का चलने का समय कम से कम हे (एन 2) है" के बराबर है "एल्गोरिथ्म एक का चलने का समय बिग ओमेगा (एन 2) है", तो यह व्यर्थ नहीं है।
O-अंकन, दूसरे शब्दों में अर्थ है: f (x) के अंतर्गत आता है हे सेट (छ (x)) अगर f (x) < सी * g (x), सभी सी के लिए (उन वास्तविक संख्याएं हैं)
यानी अपने एल्गोरिथ्म द्विघात क्रिया
यह व्यर्थ नहीं है, यह उदाहरण के लिए इस्तेमाल किया जा सकता है अगर आप सही एल्गोरिथ्म पता नहीं है की तुलना में अधिक हो जाना नहीं है, लेकिन आप निश्चित रूप से पता है कि यह हे की आवश्यकता होगी (एन^2) संचालन।
उदाहरण के लिए, यदि कोई एल्गोरिदम को सॉर्ट करने के बारे में नहीं जानता है, लेकिन समझता है कि एक सरणी को सॉर्ट करने के लिए हमें कम से कम प्रत्येक तत्व को देखने की आवश्यकता है, तो कोई यह कह सकता है कि "सरणी को सॉर्ट करना कम से कम ओ (एन) है "।
@downvoter: कोई स्पष्टीकरण? –
क्योंकि कोई भी इस बात की परवाह नहीं करता कि यह सर्वोत्तम मामले में कितनी तेजी से काम करता है, सबसे खराब मामला महत्वपूर्ण है। आम तौर पर लोग यह जानना चाहते हैं कि यह सबसे बुरी स्थिति में कितना होगा।
f(n) एल्गोरिदम के चलने का समय बनें।
=> f(n) >= O(n2)
=> f(n) >= 0 , because 0 is a member of set of functions that are O(n2)
यह हमेशा f(n) के लिए सच है, क्योंकि चलने का समय हमेशा नकारात्मक नहीं होता है। इसलिए, बयान अनावश्यक है।
ओ (एन^2) एक सबसे खराब स्थिति परिदृश्य है, जिसका अर्थ है कि ए का रन टाइम एन^2 या तेज होगा। यदि इसका रन-टाइम कम से कम ओ (एन^2) है तो इसका मतलब है कि सबसे तेज़ रन-टाइम ए हो सकता है, कम से कम ओ (एन^2) है। इसका मतलब है कि यह ओ (एन^2) से भी धीमा हो सकता है। इन बयानों का मतलब है कि ए के पास कोई भी संभावित रन-टाइम हो सकता है।
मुझे पता है कि कोई रैखिक कार्य ए + बी ओ (एन) और ओ (एन^2) भी है। क्या यह भी ओ (एन^3) है?
हाँ, यह है। बड़े-ओ नोटेशन कार्यों के पूरे संग्रह को दर्शाता है। लेकिन हमें इसे एक समारोह को यथासंभव निकटता से चिह्नित करने के लिए उपयोग करना चाहिए। हालांकि यह सच है कि f(n) = an+bO(n^2) या O(n^3) है, यह f(n) = O(n) कहने के लिए और अधिक सटीक है।
एक सादृश्य:
बयान की तरह एक सा है: "। मेरे घर की छत की ऊंचाई जो कम से कम जमीन के स्तर से है पर है" सच है, लेकिन पूरी तरह से अपरिहार्य है।
आप इस प्रश्न से किस संदर्भ में पूछते हैं? – nhahtdh
यह व्यर्थ है क्योंकि आपने कोई एल्गोरिदम ए – aqua
प्रदान नहीं किया है एल्गोरिदम ए प्रविष्टि सॉर्ट एल्गोरिदम है। – tanmoy