ट्री जटिलता और खोज

Question

शब्दों की सूची में trie बनाने की जटिलता क्या है और उस त्रिभुज में शब्द के दूसरे सेट को खोजने की जटिलता क्या है? क्या मुझे स्ट्रिंग खोज के लिए trie का उपयोग करना चाहिए, जब मेरे पास हैशटेबल है?

Answer 1

एक Trie बनाने की जटिलता O(W*L) है, जहां W शब्दों की संख्या है, और L शब्द के एक औसत लंबाई है: आप सेट में W शब्दों में से प्रत्येक के लिए औसतन L लुकअप प्रदर्शन करने की जरूरत है।

वही शब्दों को बाद में देखने के लिए चला जाता है: आप L प्रत्येक W शब्दों के लिए चरण निष्पादित करते हैं।

हैश सम्मिलन और लुकअप की एक ही जटिलता है: प्रत्येक शब्द के लिए आपको समानता की जांच करने की आवश्यकता है, जो O(L) लेता है, O(W*L) की समग्र जटिलता के लिए।

यदि आपको पूरे शब्दों को देखने की ज़रूरत है, हैश तालिका आसान है। हालांकि, आप हैश टेबल का उपयोग करके अपने उपसर्ग द्वारा शब्दों को नहीं देख सकते हैं; यदि उपसर्ग-आधारित लुकअप आपके लिए कोई रूचि नहीं रखते हैं, तो हैश तालिका का उपयोग करें; अन्यथा, एक trie का उपयोग करें।