में अंतर्निहित फ़ंक्शन की जटिलता को कैसे ढूंढें मेरे पास समस्या का विशेष मामला है, लेकिन यह जानना अच्छा होगा कि यह किसी भी फ़ंक्शन के लिए संभव है या नहीं।पायथन
तो मैं एक स्ट्रिंग में एक सबस्ट्रिंग की स्थिति खोजना चाहता हूं। ठीक है, अजगर में find method है जो वास्तव में आवश्यक है।
string.find (रों, उप [, शुरू [, अंत]])
वापसी रों में सबसे कम सूचकांक जहां सबस्ट्रिंग उप ऐसे पाया जाता है कि उप पूर्ण रों में निहित है [शुरूआत समाप्ति]। असफलता पर वापसी -1। प्रारंभ और अंत के लिए डिफ़ॉल्ट और नकारात्मक मानों की व्याख्या स्लाइस के लिए समान है।
कमाल है, लेकिन समस्या यह है कि एक बड़ा स्ट्रिंग में एक बड़ा-स्ट्रिंग खोजने O(n*m) से O(n) को चला सकते हैं depending on the algorithm (जो एक बहुत बड़ा सौदा है) है। दस्तावेज़ीकरण समय जटिलता, और अंतर्निहित एल्गोरिदम के बारे में जानकारी के बारे में कोई जानकारी नहीं देता है।
- बेंचमार्क
- स्रोत कोड के लिए जाने के लिए और समझने के लिए यह
दोनों वास्तव में आसान (मुझे आशा है कि है कि वहाँ नहीं लग कोशिश:
मैं यह कैसे हल करने के लिए कुछ दृष्टिकोण को देखने के एक आसान तरीका)। तो मैं अंतर्निहित फ़ंक्शन की जटिलता कैसे पा सकता हूं?
आप [big_o] (https://github.com/pberkes/big_O) मॉड्यूल पर एक नज़र डालना चाहते हैं। –
@AlexThornton आपको धन्यवाद धन्यवाद, लेकिन यह मूल रूप से मेरी 'बेंचमार्क' श्रेणी में आता है। न केवल यह अनुमान लगाने में लंबा है, कभी-कभी इसे प्राप्त करना मुश्किल होता है (कुछ संभाव्य एल्गोरिदम के लिए या किनारे के मामलों को प्राप्त करें)। यह सिर्फ अजीब लगता है कि यह जानकारी दस्तावेज़ीकरण में उपलब्ध नहीं है। –
यह अजीब बात है। विकी पर 'टाइम कॉम्प्लेक्सिटी' अनुभाग है जो आपको कुछ के लिए बताता है, लेकिन 'string.find() 'जैसी विधियों के लिए नहीं। –