मैं कुछ डेटा संरचनाओं के माध्यम से जा रहा था और मैंने इसे एक समय जटिलता के रूप में देखा: ओ (लॉग (लॉग (एन))) - प्रतिस्पर्धी।ओ क्या करता है (लॉग (लॉग (एन))) - प्रतिस्पर्धी मतलब?
मैंने पढ़ा कि निरंतर प्रतिस्पर्धी अपेक्षित समय/इष्टतम समय का अनुपात था। लेकिन सेट-प्रतिस्पर्धी होने का क्या अर्थ है?
ऑनलाइन एल्गोरिदम वह है जो पहले से ही अपने इनपुट को नहीं जानता है, और अप्रत्याशित इनपुट के लिए "प्रतिक्रिया" (एक अर्थ में) होना चाहिए। इसके विपरीत, ऑफ़लाइन एल्गोरिदम वे हैं जो अपने सभी इनपुट अग्रिम में जानते हैं।
प्रतियोगी विश्लेषण एक इष्टतम ऑफ़लाइन एल्गोरिथ्म के लिए एक इष्टतम ऑनलाइन एल्गोरिथ्म के प्रदर्शन की तुलना। इस प्रकार, के-प्रतिस्पर्धी का मतलब है कि एक ऑफ़लाइन एल्गोरिदम है जो ऑनलाइन एल्गोरिदम से अधिकतर के-गुना खराब होता है। तो, ओ (lglgn) प्रतिस्पर्धी का मतलब है कि इष्टतम ऑफ़लाइन एल्गोरिदम इष्टतम ऑनलाइन एल्गोरिदम की तुलना में अधिकतर lglgn (लगातार एक बार) समय पर खराब प्रदर्शन करता है।
शब्द "के-प्रतिस्पर्धी" शब्द को "के-अनुमान" शब्द के समान ही सोचा जा सकता है। एक के-सन्निकटन का अर्थ है कि अनुमानित एल्गोरिदम इष्टतम एल्गोरिदम से अधिकतर के समय में खराब होता है।
This अपने प्रश्न पर कुछ प्रकाश डाला सकता है।
एक किसी भी BST एल्गोरिथ्म होने दो, (एस करने के लिए) अनुक्रम एस और ऑप्ट प्रदर्शन की लागत के रूप एक (एस) को परिभाषित प्रदर्शन करने के लिए कम से कम लागत के रूप में:
ऊपर के लिंक से
अनुक्रम एस एक एल्गोरिद्म एक टी प्रतिस्पर्धी है यदि सभी संभव दृश्यों एस, ए (एस) < = टी * ऑप्ट के लिए (एस, करने के लिए) + O (एम, एन)।
क्या आप इस प्रश्न को बेहतर बना सकते हैं? –
क्या आप इसे कम से कम ओ (लॉग (लॉग (एन)) द्वारा सुधार सकते हैं? –