संभव डुप्लिकेट:
Big O when adding together different routinesयोग
क्या O(n) + O(log(n)) को कम करता है? मेरा अनुमान O(n) है लेकिन एक कठोर तर्क नहीं दे सकता है।
मुझे लगता है कि O(n) + O(1) को O(n) से कम करना चाहिए क्योंकि O(1) केवल स्थिर है।
खैर O(f(n)) + O(g(n)) = O (f(n) + g(n)) के बाद से हम सिर्फ एक f(n) ऐसी है कि f(n) > n + log(n)
के रूप में एन पर्याप्त log(n) < n बढ़ता है हम कह सकते हैं के बाद से गणना करने के लिए कोशिश कर रहे हैं कि f(n) > 2n > n + log(n)
इसलिए O(f(n)) = O(2n) = O(n)
एक अधिक सामान्य अर्थ में, O(f(n)) + O(g(n)) = O(f(n)) अगर कुछ स्थिर सी के लिए c*f(n)>g(n)। क्यूं कर? क्योंकि इस मामले में f(n) हमारे एल्गोरिदम पर "हावी" होगा और इसकी जटिलता को निर्देशित करेगा।
उत्तर ओ (एन) है। ओ (लॉग एन) ओ (एन) से कम है। इसलिए उनके अतिरिक्त अधिकतम मूल्य है जो ओ (एन) है।
आदेश हमेशा उच्च आदेश शर्तों तक कम हो जाता है। मैं आपको सहज तर्क दे सकता हूं। मान लें कि आपके पास O(n + n^2) है। फिर रन भाग में कौन सा हिस्सा अधिक महत्वपूर्ण भूमिका निभाएगा? एन या एन^2। जाहिर है एन^2। क्योंकि जहां एन^2 है, जब एन बढ़ता है या घट जाता है तो आप एन के प्रभाव को नहीं देख पाएंगे।
उदाहरण के रूप में,
let n = 100, then n^2 = 10000
means n is 0.99% and n^2 is 99.01% of total running time.
What would you consider for runtime?
if n is increased then this difference is clearer.
मैं तुम्हें अब समझ में लगता है,
आप अपने खुद के होमवर्क नहीं करना चाहिए? –
@Yuck क्षमा करें मुझे उस पोस्ट को नहीं मिला .. धन्यवाद –