इस घातीय एल्गोरिदम

Question

की बिग-ओ जटिलता को सरल बनाना मेरे पास एक गिनती एल्गोरिदम है जिसके लिए मैं एक सामान्य बड़ा विवरण प्राप्त करने की कोशिश कर रहा हूं। यह बहुत घोंसला और भयंकर घातीय है। संदेश यह है:

1. For each T_i in T 
2. For k = 1 to max_k 
3. For each of 2^k*(n choose k) items 
4. For each t in T_i 
5. check if the item is in t...etc. 

यहाँ प्रत्येक चलने का समय

1. यह एक सरल विभाजन है और मैं सिर्फ यह एक निरंतर c1 देने के लिए जा रहा हूँ की एक पंक्ति-दर-पंक्ति विचार है।
2. max_k एक छोटी संख्या है, हमेशा एन से कम, शायद 4 या 5 के आसपास। मैं नीचे के का उपयोग करूंगा।
3. यह लूप हमेशा 2^के * (एन का चयन करें) समय
4. लाइन 1 स्थिरता पर विचार करके, हम इस लाइन को सामान्यीकृत कर सकते हैं और जानते हैं कि यह सबसे खराब मामले में कुल 2^n बार कभी भी आग नहीं लगाएगा, लेकिन आम तौर पर 2^एन बार का एक अंश चलाएगा, इसलिए हम इसे एक (2^एन)/सी 2
5. कॉल करेंगे, यह इन सभी लूपों के अंदर सरल if-statement ऑपरेशन है, इसलिए c3।

गुणा इन सभी को एक साथ देता है:

c1 * k * 2^k * (n choose k) * (2^n)/c2 * c3 

जब से मैं एक बड़ा-ओ प्रतिनिधित्व चाहते हैं, स्थिरांक अनदेखी देता है:

k * 2^k * (n choose k) * (2^n) 

यह ज्ञात है कि (एन कश्मीर चुनें) घिरा है उपरोक्त (एन * ई/के)^के, तो:

O(k * 2^k * (n * e/k)^k * (2^n)) 

मेरी तलाश पर, मैं यहां क्या अनदेखा कर सकता हूं ... 2^n निश्चित रूप से हावी शब्द है क्योंकि एन हमेशा के मुकाबले बड़ा होता है, और आमतौर पर बहुत अधिक होता है। क्या इसे ओ (2^एन) के लिए सरल बनाया जा सकता है? या ओ (2^भयानक)? या मुझे 2^के में छोड़ना चाहिए, जैसे ओ (2^के * 2^एन) में? (या सभी शर्तों को छोड़ दें?)

मेरी समझ यह है कि यदि k या max_k प्रतिस्पर्धा या एन को पार कर सकता है, तो वे महत्वपूर्ण हैं। लेकिन चूंकि वे हमेशा प्रभुत्व रखते हैं, क्या उन्हें बहुपद चलने वाले समय के निचले क्रम की शर्तों को छोड़ दिया जा सकता है? मुझे लगता है कि सभी घातीय चलने का समय गड़बड़ मुझे भ्रमित कर रहा है। किसी भी सलाह की काफी सराहना की जाती है। जिसका अर्थ है - -

Answer 1

मेरे समझ है कि अगर कश्मीर या max_k प्रतिस्पर्धा या n को पार कर सकते हैं, तो वे महत्वपूर्ण

यह सच है, लेकिन दूसरी तरह के आसपास नहीं है यह नजरअंदाज नहीं किया जा सकता है जब वह बड़े ओ नोटेशन के लिए आता है, भले ही यह एन के साथ प्रतिस्पर्धा नहीं करता है। इसे केवल तभी अनदेखा किया जा सकता है जब max_k स्थिर से घिरा हुआ हो (वहां c है जो k <= c) है। उदाहरण के लिए - O(n * logk) एल्गोरिदम, O(n) नहीं हैं, क्योंकि के कारक को बाध्य नहीं किया गया है और इस प्रकार k जैसे प्रत्येक निरंतर c के लिए मौजूद है।

चूंकि आपको मिली अभिव्यक्ति एक उत्पाद है, इसलिए आप अनदेखा कर सकते हैं, जो आपके मामले में हैं - केवल e आपको O(k*2^k * (n/k)^k * 2^n) प्राप्त कर रहा है।

तो kहै घिरा है, तो आप यह अभिव्यक्ति के रूप में अच्छी तरह से में बड़ी हे संकेतन से निकाल सकते हैं, और आप O(n^k* 2^n) मिल जाएगा।ध्यान दें कि इस मामले में, हालांकि n^k << 2^n, फिर भी इसे अनदेखा नहीं किया जा सकता है, क्योंकि प्रत्येक निरंतर सी के लिए कुछ n मौजूद हैं जैसे c*2^n < n^k *2^n, इसलिए एल्गोरिदम O(2^n) एक नहीं है।

अतिरिक्त कारकों को जोड़ने के लिए अनदेखा किया जा सकता है। यदि k < n तो O(n + k) = O(n), क्योंकि एक स्थिरांक c,N है, तो सभी n > N: c*n < n + k के लिए, लेकिन यह निश्चित रूप से उत्पाद से निपटने पर सही नहीं है।