एल्गोरिदम

Question

के चलने वाले समय की तुलना करने के लिए आलेखों और एसिम्प्टोटिक विश्लेषण के बीच अंतर यह प्रश्न काफी कहता है कि मैं क्या पूछ रहा हूं।

मेरे पास एक एल्गोरिदम है और मैं घूम रहा था कि एक 'बिग-ओह' चलने का समय प्राप्त करने के लिए बेहतर तरीका क्या है - एक ग्राफ के माध्यम से और चलने वाले समय के विरुद्ध इनपुट की संख्या या एसिम्प्टोटिक विश्लेषण के माध्यम से?

मेरी ग्राफ के लिए मैं वर्तमान में उपयोग कर रहा हूँ:

private int startTime = System.currentTimeMillis(); //At start of algorithm 
private int endTime = System.currentTimeMillis(); //At the end of algorithm 
int runningTime = endTime - startTime; 

'को मापने' एक alogrithm का चलने का समय के दोनों तरीकों के बीच क्या अंतर है?

Answer 1

"अनुभवसिद्ध" (इनपुट के आकार के खिलाफ रन टाइम साजिश) के साथ समस्या यह केवल प्रदान की परीक्षण का मामला के लिए काम करते हैं।

"सैद्धांतिक" विश्लेषण आपको एल्गोरिदम के सभी नुकसान देता है, आप गणित का उपयोग करके वास्तविक सर्वोत्तम मामले/औसत मामले/... का विश्लेषण कर सकते हैं, और यह सही होने की गारंटी है।

एक अच्छा सामान्य उदाहरण जो काफी तेजी से आम तौर पर है simplex algorithm है, है, लेकिन कुछ इनपुट के लिए कभी-कभी घातीय सबसे खराब स्थिति बार चलाने करता है।

दूसरी ओर, asymptotic विश्लेषण अनदेखी स्थिरांक की वजह से है, और केवल "बड़ा पर्याप्त आदानों" के लिए लागू होते हैं, वे काफी बेकार है अगर इनपुट अपेक्षाकृत छोटे होने की उम्मीद है कर रहे हैं, और यह 2 एल्गोरिदम के बीच अंतर करना मुश्किल है एक ही जटिलता वर्ग में, लेकिन विभिन्न स्थिरांक के साथ, और निरंतर उत्पादन कोड में कोई फर्क नहीं पड़ता।

tl; dr: प्रत्येक का अपना उपयोग होता है, और दोनों संयोजन संयोजन केवल उनमें से एक का उपयोग करने से बेहतर परिणाम देता है।

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