algorithm - हरण - संस्कृत में प्रत्यय कितने प्रकार के होते हैं



एक प्रत्यय वृक्ष के निर्माण की जटिलता (1)

एक प्रत्यय वृक्ष बनाने के लिए, सबसे बुरे मामले में यदि स्ट्रिंग के सभी पत्र अलग हैं तो जटिलता कुछ ऐसी होगी

n + (n-1) + (n-2) ... 1 = n*(n+1)/2

जो ओ (एन ^ 2) है।

हालांकि http://en.wikipedia.org/wiki/Suffix_tree अनुसार एक प्रत्यय वृक्ष ओ (एन) समय लेता है। मुझे यहां क्या समझ नहीं आ रहा है?


एल्गोरिदम क्यों होना चाहिए इसके पीछे आपका अंतर्ज्ञान Θ (एन 2 ) होना अच्छा है, लेकिन अधिकांश प्रत्यय पेड़ इस तरह से डिजाइन किए गए हैं जो इस समय जटिलता की आवश्यकता को समाप्त करता है। सहजता से, ऐसा लगता है कि आपको विभिन्न भिन्न प्रत्ययों को पकड़ने के लिए Θ (एन 2 ) अलग-अलग नोड्स की आवश्यकता है, क्योंकि आपको एन + (एन -1) + ... + 1 अलग-अलग नोड्स की आवश्यकता होगी। हालांकि, प्रत्यय पेड़ आम तौर पर डिजाइन किए जाते हैं ताकि प्रत्यय में प्रति चरित्र एक नोड न हो। इसके बजाए, प्रत्येक किनारे को आमतौर पर वर्णों के अनुक्रम के साथ लेबल किया जाता है जो मूल स्ट्रिंग के सबस्ट्रिंग होते हैं। यह अभी भी प्रतीत हो सकता है कि आपको इस पेड़ को बनाने के लिए Θ (एन 2 ) समय की आवश्यकता होगी क्योंकि आपको इन किनारों पर सबस्ट्रिंग्स को कॉपी करना होगा, लेकिन आम तौर पर यह एक प्यारा चाल से बचा जाता है - क्योंकि सभी किनारों को लेबल किया जाता है स्ट्रिंग्स जो इनपुट के सबस्ट्रिंग्स हैं, किनारों को इसके बजाय प्रारंभ और अंत स्थिति के साथ लेबल किया जा सकता है, जिसका अर्थ है कि किनारे ()) अक्षरों को विस्तारित करने के लिए ओ (1) समय में और ओ (1) स्पेस का उपयोग किया जा सकता है।

उस ने कहा, प्रत्यय पेड़ों का निर्माण अभी भी करना मुश्किल है। विकिपीडिया में संदर्भित Θ (एन) एल्गोरिदम आसान नहीं हैं। रैखिक समय में काम करने वाले पहले एल्गोरिदम में से एक Ukkonen के एल्गोरिदम है , जिसे आमतौर पर स्ट्रिंग एल्गोरिदम पर पाठ्यपुस्तकों में वर्णित किया जाता है (जैसे स्ट्रिंग्स, पेड़ और अनुक्रमों पर एल्गोरिदम ) । मूल कागज विकिपीडिया में जुड़ा हुआ है। अधिक आधुनिक दृष्टिकोण पहले एक प्रत्यय सरणी बनाने और उसके बाद प्रत्यय पेड़ का निर्माण करने के लिए काम करते हैं।

उम्मीद है की यह मदद करेगा!





suffix-tree