9
क्या एक String.indexof() फ़ंक्शन कॉललागत/एक String.indexof() फ़ंक्शन कॉल की जटिलता क्या है
A
उत्तर
0
जावा में की लागत/जटिलता है, अगर कॉल string1.indexOf (string2) है समय लागत ओ (एम - एन) होगी जहां मीटर स्ट्रिंग 1 की लंबाई है और n स्ट्रिंग 2 की लंबाई है। .indexOf() की
9
IIRC जावा के कार्यान्वयन सिर्फ naive string matching algorithm है, जो O(n+m) औसत और O(n*m) सबसे खराब स्थिति है।
अभ्यास में यह पर्याप्त तेज़ है; मैंने अपेक्षाकृत बड़ी सुई (> 500 चार) और घास के मैदान (कुछ एमबी) तारों के लिए इसका परीक्षण किया और यह एक दूसरे के अंदर मिलान (औसत घरेलू कंप्यूटर में) करेगा। आपको याद है कि मैंने इसे पूरे घास के मैदान से गुजरने के लिए मजबूर किया।
+0
का डुप्लिकेट मुझे पता है कि यह बहुत समय पहले है, लेकिन क्या आप जानते हैं कि आपको यह कहां से मिला है? मुझे अपने स्नातक थीसिस के लिए उस जानकारी की आवश्यकता होगी और मुझे नहीं पता कि स्टैक ओवरफ्लो थीसिस के लिए स्वीकार्य संदर्भ होगा;) – odaa
+0
@odaa मैंने कुछ प्रयोग चलाए और कॉलेज में होने पर एक पेपर लिखा। – NullUserException
+0
@NullUserException, आप क्यों कहते हैं कि 'ओ (एन + एम) 'औसत मामला है? http://stackoverflow.com/a/12752295/632951 उस बिंदु के विपरीत प्रतीत होता है। – Pacerier
0
कार्यान्वयन पर निर्भर करता है।
उदाहरण के लिए, जब एक लंबे समय तक स्ट्रिंग के भीतर एक स्ट्रिंग के लिए खोज, "टर्बो बोयर-मूर एल्गोरिथ्म का अतिरिक्त स्थान निरंतर राशि (के रूप में बोयर-मूर के लिए 3N के खिलाफ) 2n तुलना के भीतर एक खोज को पूरा करने लगते हैं, जहां एन खोजे जाने वाले पाठ में वर्णों की संख्या है। " (Wikipedia देखें)।
+1
@caleb: वास्तव में, आप सवाल से कैसे कह सकते हैं? –
संबंधित मुद्दे
- 1. लॉग फ़ंक्शन की जटिलता क्या है?
- 2. OrderedDictionary की जटिलता क्या है?
- 3. नींद की तरह की जटिलता क्या है?
- 4. PHP फ़ंक्शन स्ट्रेलन की एल्गोरिदमिक जटिलता()
- 5. नियमित अभिव्यक्ति की जटिलता क्या है?
- 6. क्या वेक्टर की जटिलता :: स्पष्ट अनिर्दिष्ट है?
- 7. ग्रुपबी ऑपरेशन की एसिम्प्टोटिक जटिलता क्या है?
- 8. सी ++ में set_intersection की जटिलता क्या है?
- 9. स्विच स्टेटमेंट की रनटाइम जटिलता क्या है?
- 10. ट्रीसेट पुनरावृत्ति की समय जटिलता क्या है?
- 11. मैट्रिक्स अतिरिक्तता की जटिलता क्या है?
- 12. योजना में इस कार्य की समय जटिलता क्या है?
- 13. इस स्ट्रिंग मैनिपुलेशन कोड की स्पेस जटिलता क्या है?
- 14. फ़ंक्शन कॉल में "()" का अर्थ क्या है?
- 15. जावा में लिंक्डलिस्ट पर आकार() कॉल की समय जटिलता क्या है?
- 16. एल्गोरिदम की जटिलता
- 17. random.sample की समय जटिलता
- 18. इनलाइन फ़ंक्शन कॉल का क्या फायदा है?
- 19. ल्यूसीन की खोज की जटिलता
- 20. सेट की जटिलता :: डालने
- 21. चक्रवात जटिलता की गणना
- 22. फ़ंक्शन पॉइंटर बनाम फ़ंक्शन कॉल के बीच क्या अंतर है?
- 23. फ़ंक्शन कॉल से फ़ंक्शन कॉल नाम निकालने
- 24. पेड़ के ट्रैवर्सल की समय जटिलता क्या है?
- 25. क्लोजर में गिनती कार्य की समय जटिलता क्या है?
- 26. जावा में हैश मैप.containsKey() की समय जटिलता क्या है?
- 27. ट्रीसेट में आदेशित संचालन की समय जटिलता क्या है?
- 28. रूबी में ऐरे # यूनिक विधि की समय जटिलता क्या है?
- 29. std :: map में find() की समय जटिलता?
- 30. प्राथमिकता की जटिलता QAue addAll()
किस भाषा में है, और क्या की तुलना में? फ़ंक्शन के तर्क क्या हैं - क्या यह एक स्ट्रिंग, एक char, एक कस्टम तुलनाकर्ता लेता है? – Kobi
क्या यह जावा है जिसके बारे में आप बात कर रहे हैं? – NullUserException
http://stackoverflow.com/questions/12752274/java-indexofstring-str-method-complexity –