क्या ओ (लॉगन) हमेशा एक पेड़ है?

Question

हम हमेशा एक (द्विआधारी खोज) पेड़ पर संचालन देखते हैं ओ पेड़ की वजह से ओ (लॉगन) सबसे खराब केस चलने का समय होता है। मुझे आश्चर्य है कि अगर हमें बताया जाता है कि एक एल्गोरिदम ने लॉगन के कार्य के रूप में समय चल रहा है, उदाहरण के लिए एम + nlogn, क्या हम निष्कर्ष निकाल सकते हैं कि इसमें एक (संवर्धित) पेड़ शामिल होना चाहिए?

संपादित करें: आपकी टिप्पणियों के लिए धन्यवाद, अब मुझे लगता है कि विभाजन-विजय और बाइनरी पेड़ इतनी समान दृष्टि/अवधारणात्मक हैं। मैंने दोनों के बीच कभी कनेक्शन नहीं बनाया था। लेकिन मैं ऐसे मामले के बारे में सोचता हूं जहां ओ (लॉगन) एक विभाजन-अलगाव नहीं है जिसमें एक पेड़ शामिल है जिसमें बीएसटी/एवीएल/लाल-काले पेड़ की कोई संपत्ति नहीं है।

यह खोज/संघ संचालन के साथ पृथक सेट डेटा संरचना है, जिसका चलने का समय ओ (एन + एमएलओएनएन) है, जिसमें एन तत्वों का # है और एम खोजें ऑपरेशन की संख्या है।

अगर मुझे sth याद आ रही है तो कृपया मुझे बताएं, लेकिन मैं नहीं देख सकता कि विभाजन कैसे जीतता है। मैं बस इस (विवादित सेट) मामले में देखता हूं कि इसमें कोई बीएसटी संपत्ति वाला पेड़ है और एक रनिंग समय लॉगएन का कार्य है। तो मेरा सवाल यह है कि मैं इस मामले से सामान्यीकरण क्यों कर सकता हूं।

Answer 1

आपके पास बिल्कुल पीछे है। O(lg N) आम तौर पर कुछ प्रकार का विभाजन और एल्गोरिदम जीतने का मतलब है, और विभाजन और जीत को लागू करने का एक आम तरीका एक बाइनरी पेड़ है। जबकि बाइनरी पेड़ सभी विभाजित और जीतने वाले एल्गोरिदम का एक बड़ा सबसेट हैं, वैसे भी एक सबसेट हैं।

कुछ मामलों में, आप अन्य विभाजन को बदल सकते हैं और एल्गोरिदम को सीधे बाइनरी पेड़ों में जीत सकते हैं (उदाहरण के लिए किसी अन्य उत्तर पर टिप्पणियां पहले ही बाइनरी खोज का दावा करने का प्रयास कर चुकी हैं)। बस एक और स्पष्ट उदाहरण के लिए, हालांकि, एक मल्टीवे पेड़ (उदा। बी-पेड़, बी + पेड़ या बी * पेड़), जबकि स्पष्ट रूप से एक पेड़ स्पष्ट रूप से एक बाइनरी पेड़ नहीं है।

फिर, अगर आप बुरी तरह से पर्याप्त है, तो आप का कहना है कि बहु तरफ़ा पेड़ एक द्विआधारी पेड़ एक विकृत संस्करण की तरह के रूप में प्रतिनिधित्व किया जा सकता है खिंचाव कर सकते हैं करना चाहते हैं। यदि आप चाहते हैं, तो आप शायद यह कहने के बिंदु पर सभी अपवादों को फैला सकते हैं कि उनमें से सभी बाइनरी पेड़ (कम से कम कुछ) हैं। कम से कम मेरे लिए, हालांकि, जो कुछ करता है वह "द्विआधारी पेड़" को "विभाजन और जीत" के समानार्थी बनाता है। दूसरे शब्दों में, आप जो कुछ भी पूरा करते हैं वह शब्दावली को मार रहा है और अनिवार्य रूप से एक शब्द को समाप्त कर रहा है जो कि दोनों अलग और उपयोगी है।

Answer 2

नहीं, आप एक क्रमबद्ध सरणी (उदाहरण के लिए) बाइनरी भी खोज सकते हैं। लेकिन के लिए यह http://en.wikipedia.org/wiki/Binary_search_algorithm

Answer 3

एक काउंटर उदाहरण के रूप में मेरे वचन नहीं लेते हैं:

given array 'a' with length 'n' 
y = 0 
for x = 0 to log(length(a)) 
    y = y + 1 
return y 

रन टाइम हे (लॉग (एन)), लेकिन कोई पेड़ यहाँ है!

Answer 4

लॉगरिदमिक समय लेने वाले एल्गोरिदम आमतौर पर बाइनरी पेड़ पर संचालन में पाए जाते हैं।

ओ (logn) के उदाहरण:

• एक द्विआधारी खोज या एक संतुलित खोज पेड़ के साथ एक क्रमबद्ध सरणी में एक आइटम ढूँढना।

• बायसेक्शन द्वारा क्रमबद्ध इनपुट सरणी में एक मान देखें।

Answer 5

उत्तर नहीं है। एक क्रमबद्ध सरणी की बाइनरी खोज O(log(n)) है।

Answer 6

हे के रूप में (लॉग (एन)) केवल एक ऊपरी बाध्य भी सभी हे (1) function (a, b) return a+b; तरह एल्गोरिदम हालत को संतुष्ट है।

लेकिन मैं सब थीटा (लॉग (एन)) इस बात से सहमत करने के लिए एल्गोरिदम थोड़े पेड़ एल्गोरिदम की तरह लग रहे या कम से कम एक पेड़ से निकाला जा सकता है।

Answer 7

लघु उत्तर: एक एल्गोरिथ्म लॉग (एन) ने अपने विश्लेषण के भाग के रूप है

सिर्फ इसलिए कि इसका मतलब यह नहीं है कि एक पेड़ शामिल है। उदाहरण के लिए, निम्नलिखित एक बहुत ही सरल एल्गोरिथ्म है कि है O(log(n)

for(int i = 1; i < n; i = i * 2) 
    print "hello"; 

आप देख सकते हैं, कोई पेड़ शामिल किया गया था है। जॉन, सॉर्ट किए गए सरणी पर बाइनरी खोज कैसे किया जा सकता है, इस पर एक अच्छा उदाहरण भी प्रदान करता है। ये दोनों हे लेने (लॉग (एन)) समय है, और वहाँ अन्य कोड उदाहरण है कि या बनाया जा सकता है संदर्भित कर रहे हैं। तो एसिम्प्टोटिक समय जटिलता के आधार पर धारणाएं न बनाएं, सुनिश्चित करने के लिए कोड को देखें।

अधिक पेड़ पर:

सिर्फ इसलिए कि एक एल्गोरिथ्म "पेड़" शामिल O(logn) या तो संकेत नहीं करता है। आपको पेड़ के प्रकार और ऑपरेशन पेड़ को कैसे प्रभावित करता है, उसे जानने की जरूरत है।

कुछ उदाहरण:

• उदाहरण 1)

लगाते या निम्न असंतुलित पेड़ खोज O(n) होगा।

• उदाहरण 2)

लगाते या खोज निम्नलिखित संतुलित पेड़ दोनों होगा O(log(n)) द्वारा।

संतुलित बाइनरी ट्री:

डिग्री 3 की बैलेंस्ड ट्री:

अतिरिक्त टिप्पणियाँ

पेड़ आप की जरूरत नहीं है प्रयोग कर रहे हैं एक अच्छा है की तुलना में "संतुलन" का एक तरीका है नहीं कि आपका संचालन O(n) समय नहीं O(logn) हो जाएगा। आप पेड़ों कि आत्म संतुलन कर रहे हैं का उपयोग करते हैं, तो सामान्य रूप से अधिक समय लग आवेषण, पेड़ों के संतुलन सामान्य रूप से डालने के चरण के दौरान होते हैं।