एन-आरी पेड़ में कई नोड्स का सबसे कम आम पूर्वज

I am trying to implement LCA of multiple nodes in an n-ary tree in java. I am working with parse trees of sentences, So its reasonable to assume that number of children of a node <= 6. Multiple nodes here are two phrases(continuous word sequence) in a sentence. Let k be the number of nodes involved.

एक तरीका है के/2 जोड़े के लिए दो नोड्स के एलसीए को ढूंढना और हमें के/2 नोड्स मिलेंगे। अब इन के/2 नोड्स पर भर्ती करें। आदेश ओ (nlog k) होगा, जहां ओ (एन) रैखिक एलसीए खोज एल्गोरिदम की जटिलता है। क्या मैं इसे और अधिक कुशलतापूर्वक कर सकता हूं?

0
जोड़ा संपादित
विचारों: 1
@VSOverFlow मेरे पास लॉग (के) चरण होंगे और प्रत्येक चरण ओ (एन) लेता है, इसलिए, कुल मिलाकर ओ (nlog k)। आपकी गणना में ओ (के) क्या है?
जोड़ा लेखक damned, स्रोत
मुझे लगता है कि जटिलता ओ (एन। के) नहीं है ओ (एन लॉग (के))। आपके पास के/2, के/4 के लॉग (के) चरण होंगे .. जो ओ (के) है।
जोड़ा लेखक VSOverFlow, स्रोत
मुझे लगता है कि एलसीए (2, एन) ओ (एन) है। जब आप बाइनरी पेड़ बनाते हैं तो एलसीए कॉल की कुल संख्या ओ (के) (के/2 + के/4 + ....) होती है। तो कुल रनटाइम जटिलता ओ (एन * के) है (यानी ओ (एन) की कॉल)। प्रत्येक लॉग (के) चरणों में कई ओ (एन) चरण होते हैं (के/2, के/4, के/8, ...)
जोड़ा लेखक VSOverFlow, स्रोत

1 उत्तर

मैंने इस तथ्य का उपयोग करके समस्या हल की कि वाक्यांशों के नोड्स निरंतर हैं यानी एक पार्स पेड़ के पत्ती नोड्स की सूची में निरंतर सूचकांक हैं।

segment1 को start1 से end1 में इंडेक्स दें। segment2 = (start2, end2) के लिए भी मामला है।

(start1, end1) और (start2, end2) के आवश्यक सामान्य पूर्वजों को सूचकांक min (start1, start2) और <�कोड> अधिकतम (end1, end2) ।

0
जोड़ा
विचार यह है कि यदि सभी नोड्स लगातार पत्ते नोड्स होते हैं, तो इन सभी नोड्स का एलसीए पहले और अंतिम नोड का एलसीए होगा।
जोड़ा लेखक damned, स्रोत
क्या आप पूरी विधि दे सकते हैं? मैं आपके एल्गोरिदम को वास्तविक कोड में परिवर्तित करने में सक्षम नहीं हूं।
जोड़ा लेखक javafan, स्रोत