8
मैं एक कार्यात्मक डेटा संरचना की तलाश में हूं जो दो प्रकार के बीच परिमित विभाजन का प्रतिनिधित्व करता है, जो अंतरिक्ष-कुशल और समय-कुशल है।परिमित bijections के लिए कुशल कार्यात्मक डेटा संरचना
- तत्वों की एक नई जोड़ी के साथ च विस्तार जटिलता ओ (ln एन)
- क्वेरी करने f (x है:
उदाहरण के लिए, मैं खुश अगर, एक द्विभाजन आकार n का च पर विचार होगा) या च^-1 (एक्स) है जटिलता ओ (ln एन)
- च के लिए आंतरिक प्रतिनिधित्व अधिक स्थान 2 परिमित नक्शे (च और उसके व्युत्क्रम का प्रतिनिधित्व)
मैं के बारे में पता कर रहा हूँ की तुलना में कुशल है क्रमपरिवर्तन का कुशल प्रतिनिधित्व एस, this paper की तरह, लेकिन यह मेरी समस्या का समाधान नहीं लगता है।
दो सीमित नक्शे होने के कारण सुंदर स्थान कुशल है ... यह ओ (एन) स्थान है। मैं कल्पना नहीं कर सकता कि आप उससे बेहतर कर सकते हैं। –
दो सीमित नक्शे के साथ शुरू करें, और जब आप स्मृति से बाहर निकलें तो कुछ और चालाक के बारे में चिंता करें। हैशमैप्स अच्छे हैं, अगर आप दो प्रकार हैंश कर सकते हैं। – augustss
ऐसा लगता है कि आपका फ़ंक्शन कड़ाई से मोनोटोन है, तो आप दोनों फ़ंक्शन और उलटा दोनों के लिए एक ही पेड़ खोज सकते हैं। यह एक लंबा शॉट है, मुझे लगता है। –