मैं सोच रहा हूँ कि कैसे की गणना करने के लिए अंतरिक्ष की जटिलता trie संरचना है । के रूप में मैं किया गया है की गणना है कि अगर गहराई(लंबाई के शब्द) है N और पैटर्न आकार कश्मीर(छोटे अक्षर 26) और शब्दों की संख्या: W के रूप में प्रति मेरी समझ है, यह होना चाहिए: कश्मीर^N
जबकि कई स्थानों पर यह लिखा है कि WxKxN.
आप पर प्रकाश डालेंगे जो सही है और कैसे?
सबसे खराब मामला है, यह होना चाहिए O(कश्मीर^N)
चलो मान लेते हैं कि शब्द की लंबाई 1 है, तो एक एकल सरणी के आकार कश्मीर के लिए पर्याप्त होगा ।
पूर्व : 'बी' (स्थिति = 1) कश्मीर = [नल, सूचक करने के लिए एक और सरणी के आकार k, null, null, null, ........]
चलो मान लेते हैं कि शब्द की लंबाई 2 है, तो हम करने के लिए की जरूरत है की एक सरणी के आकार k अक्षर से प्रत्येक के लिए जो कर रहे हैं में पहले स्थान पर शब्द
पूर्व: 'बा'
स्तर 1 ('बी') : [अशक्त, सूचक एक सरणी के लिए (यह कॉल की सुविधा देता Z) स्तर 2 में, null, null, null, ......]
स्तर 2: Z (दूसरा चरित्र 'ए') : [सूचक करने के लिए एक और सरणी के आकार k, null, null, .......]
चलो कहना है कि हम कर रहे हैं डालने 'bc' तो हम जा रहे हैं करने के लिए है एक और सरणी के आकार कश्मीर के लिए 'c' पर स्थिति 3 (संभालने आप कर रहे हैं डालने 'एक' 0 पर है, तो 'बी' पर 1, और इतने पर)
इसलिए प्रत्येक स्तर पर 0, हम आकार की एक सरणी कश्मीर (आकार पर स्तर 0: कश्मीर), स्तर 2 में हम कश्मीर सरणी के आकार की कश्मीर (आकार पर स्तर 1: k^2), स्तर 3 में हम एक k^2 नंबर की सरणी के आकार की कश्मीर (आकार पर स्तर 3: कश्मीर^3), और इतने पर ।
तो अंतरिक्ष जटिलता हो जाएगा k + k^2 + k^3 + ..... कश्मीर^N (N है शब्द की लंबाई). यह है सबसे ज्यादा मामले समय जटिलता है ।
