मैं एक परियोजना पर काम कर रहा हूं, और चलने वाले समय को अनुकूलित करने की आवश्यकता है। String.contains() रनटाइम TreeSet.contains() जैसा है, जो ओ (लॉगएन) है?जावा में String.contains() का बिग-ओ क्या है?
कारण मैं पूछ रहा हूँ मैं एक TreeMap<String, TreeSet<Song>>, जहां गीत गीत की एक स्ट्रिंग को शामिल निर्माण कर रहा हूँ है। दक्षता के आधार पर, मैं गीत के अंदर गीत शब्दों का एक सेट और स्ट्रिंग के बजाए उस पर चल रही खोजों सहित विचार कर रहा हूं।
सर्वोत्तम ज्ञात एल्गोरिथम में से एक Boyer-Moore स्ट्रिंग खोज एल्गोरिथ्म जो हे (एन) है, हालांकि यह सबसे अच्छा मामले में sublinear प्रदर्शन देने के कर सकते हैं।
कौन सा एल्गोरिथ्म जावा में प्रयोग किया जाता है जो implemetation आप डाउनलोड पर निर्भर करता है। ऐसा लगता है कि उदाहरण के लिए ओपनजेडीके एक बेवकूफ एल्गोरिदम का उपयोग करता है जो सर्वोत्तम मामले में ओ (एनएम) और रैखिक प्रदर्शन में चलता है। लाइनें 1770-1806 here देखें।
जो लेख आपने लिंक किया है, वह ओ (एन) है क्योंकि यह अधिकतम 3 एन तुलना करता है। सुधार के लिए धन्यवाद: - "सबसे खराब स्थिति हे (एन)" एक टॉटोलॉजी परिभाषा हे द्वारा (एन) सबसे ज्यादा मामले :) –
@Nicholas व्हाइट है। –
jdk1.6.0_23, एक ही 'String.indexOf()' एक समकालीन OpenJDK के रूप में कार्यान्वयन था https://programmers.stackexchange.com/questions/65558/why-does-javas-string-class-not- के अनुसार कार्यान्वयन-एक-अधिक-कुशल-सूचकांक। कोई आपको बता सकता है कि क्या यह 'स्ट्रिंग.contains() ' – rakslice
तुम भी बजाय एक Trie का उपयोग कर एक ट्री-मैप की कोशिश कर सकते हैं (हालांकि जावा में कोई अंतर्निहित Trie कार्यान्वयन)
[Trie संदर्भ] (https://www.topcoder.com/community/data-science/data-science-tutorials/using-tries/) – cellepo
एक झटका या कुछ भी लेकिन बनने की कोशिश कर नहीं: यह क्यों प्रोफ़ाइल नहीं? –
यदि मेरे पास परीक्षण के लिए समय है, शायद। एक और परीक्षण है जिसे मैं प्रोजेक्ट के साथ चलाने के लिए चाहता हूं: पेड़ और हैशसेट के बीच रनटाइम भिन्नताएं। अगर दिन में 30 घंटे थे, तो अभी भी सबकुछ के लिए पर्याप्त समय नहीं होगा! – Jason