क्या कोई उपकरण है जो बिग-ओ जटिलता के लिए प्रदर्शन कोड विश्लेषण निर्धारित कर सकता है?

Question

मैंने वहां कुछ भी नहीं देखा है, और मुझे जटिल रूप से जटिल कार्य का विश्लेषण करने के लिए "एन" को परिभाषित करने में कठिनाई पर संदेह है, क्योंकि परिभाषित करने के लिए केवल एक या दो चर से अधिक होगा।

चक्रवात जटिलता के लिए विश्लेषण उपकरण हैं लेकिन समय (और/या अंतरिक्ष) जटिलता के लिए हैं? यदि ऐसा है, तो नहीं, क्यों नहीं? क्या यह अक्षम है? असंभव? किसी को बस इसके आसपास नहीं मिला है?

आदर्श रूप में वहाँ आवेदन के लिए समग्र जटिलता की तरह कुछ (विभिन्न संभव "n" रों को परिभाषित) के रूप में अच्छी तरह से अनुप्रयोग में प्रत्येक विधि के लिए के रूप में

संपादित होगा: तो ऐसा लगता है जैसे एक सटीक समाधान असंभव है क्योंकि Halting Problem के बावजूद, कुछ प्रकार की ह्युरिस्टिक अनुमान संभव है? मुझे एहसास है कि व्यावहारिक उद्देश्यों के लिए एक अच्छा प्रोफाइलर अधिक उपयोगी जानकारी देगा, लेकिन यह एक दिलचस्प समस्या की तरह लगता है।

इसके अलावा, प्रोग्राम के एक निश्चित सबसेट के लिए गणना करने वाले व्यक्ति के बारे में कैसे?

Answer 1

दुर्भाग्य से इस समस्या Halting problem कहा जाता है ...

Answer 2

नहीं, यह संभव नहीं हॉल्टिंग समस्या की वजह से है,।

यदि आप अपने अनुप्रयोगों को बेहतर बनाने के लिए ऐसा करना चाहते हैं, तो आप इसके बजाय प्रोफाइलिंग पर विचार कर सकते हैं। यह आपको वास्तव में सबसे अधिक समय ले रहा है कि पिन-पॉइंट करने की अनुमति देगा। इस तरह आप ओ (एन^3) एल्गोरिदम अनुकूलित करने में समय नहीं व्यतीत करते हैं जो केवल छोटे डेटासेट पर चलता है।

Answer 3

ऐसा करने के लिए कभी भी कोई टूल नहीं देखा गया है, लेकिन हम बेहतर विचार पाने के लिए प्रोफाइलिंग टूल का उपयोग करते हैं जहां बाधाएं हैं। यह हमेशा स्पष्ट नहीं होता है और मैं कुछ चीजों से आश्चर्यचकित हूं कि मैंने सोचा कि वास्तव में बहुत कम समय ले रहा है और इसके विपरीत। .NET दुनिया में, मैंने ANTS और JetBrains उपकरण का उपयोग किया है।

Answer 4

कुछ thoughs:

रियल कंप्यूटर लगभग नियतात्मक परिमित स्थिति मशीनें हैं, तो हॉल्टिंग समस्या वास्तव में एक व्यावहारिक सीमा नहीं है। एक व्यावहारिक सीमा एक एल्गोरिदम है जो विश्लेषण की किसी भी क्रूर बल विधियों को सत्तारूढ़ करने, प्रतीक्षा करने की तरह महसूस करने के लिए अधिक समय लेती है।

एल्गोरिदम की जटिलता का कोई अंदाजा पाने के लिए, आप इसे हमेशा यादृच्छिक इनपुट के सेट पर चला सकते हैं और समय निकालने के उपाय कर सकते हैं। फिर डेटा के माध्यम से एक वक्र प्लॉट करें।

एल्गोरिदम की समय जटिलता का विश्लेषण करना काफी जटिल हो सकता है, जिसके लिए कुछ रचनात्मक कदमों की आवश्यकता होती है। (Quicksort के उदाहरण विश्लेषण के लिए देखें)। समस्या तार्किक प्रमेय सिद्ध करने और प्रोग्राम सत्यापन के लिए बारीकी से संबंधित है। एक उपयोगी उपकरण बनाने के लिए संभव हो सकता है जो जटिलता के अर्द्ध स्वचालित समाधान को सक्षम बनाता है, यानी एक उपकरण जो मानव से संकेत दिए गए समाधानों के लिए व्यवस्थित रूप से खोज करता है, लेकिन यह निश्चित रूप से आसान नहीं है।