एक परीक्षण समय जटिलता "प्रयोगात्मक" कैसे कर सकता है?

Question

यह देखने के लिए काउंटर को रखकर किया जा सकता है कि एल्गोरिदम कितने पुनरावृत्तियों से गुज़रता है, या समय अवधि को रिकॉर्ड करने की आवश्यकता होती है?

Answer 1

एल्गोरिथ्म जटिलता के रूप में परिभाषित किया गया है (जैसे :)

संचालन की संख्या एल्गोरिथ्म अपने इनपुट आकार के एक समारोह के रूप में करता है कुछ। एल्गोरिथ्म, - (10 तत्वों, 100 तत्वों आदि छँटाई कोशिश यानी प्रकार के लिए) और प्रत्येक आपरेशन (जैसे काम, वेतन वृद्धि, गणितीय प्रक्रिया आदि) गिनती

तो तुम विभिन्न इनपुट आकार के साथ अपने एल्गोरिथ्म प्रयास करने की आवश्यकता कर देता है।

यह आपको एक अच्छा "सैद्धांतिक" अनुमान देगा।
यदि आप दूसरी ओर वास्तविक जीवन संख्या चाहते हैं - profiling का उपयोग करें।

Answer 2

हां।

आप दोनों वास्तविक प्रदर्शन और पुनरावृत्तियों की संख्या को ट्रैक कर सकते हैं।

Answer 3

क्या मैं एएनटीएस प्रोफाइलर का उपयोग करने का सुझाव दे सकता हूं। जब आप अपने ऐप को "प्रयोगात्मक" डेटा के साथ चलाते हैं तो यह आपको इस तरह की जानकारी प्रदान करेगा।

Answer 4

वास्तव में आपके एल्गोरिदम द्वारा किए गए "संचालन" की संख्या को गिनने का सबसे अच्छा तरीका होगा। "ऑपरेशन" की परिभाषा भिन्न हो सकती है: क्विकॉर्ट जैसे एल्गोरिदम के लिए, यह दो संख्याओं की तुलना की संख्या हो सकती है।

आप किसी न किसी अनुमान के लिए आपके कार्यक्रम द्वारा उठाए गए समय को माप सकते हैं, लेकिन विभिन्न कारक वास्तविक मूल्य गणितीय जटिलता से भिन्न हो सकते हैं।

Answer 5

वर्तमान में स्वीकृत आपको कोई सैद्धांतिक अनुमान नहीं देगा, जब तक कि आप प्रयोगात्मक रूप से मापा गया समय फिट करने में सक्षम नहीं होते हैं जो उन्हें अनुमानित करता है। यह उत्तर आपको ऐसा करने के लिए एक मैन्युअल तकनीक देता है और उस अंतर को भरता है।

आप एल्गोरिदम के सैद्धांतिक जटिलता समारोह अनुमान लगाते हैं। आप तेजी से बड़ी समस्याओं के लिए वास्तविक जटिलता (परिचालन, समय, या जो भी आपको व्यावहारिक पाते हैं) का प्रयोगात्मक रूप से मापते हैं।

उदाहरण के लिए, मान लें कि एक एल्गोरिदम वर्ग है। समय को मापें (कहें), और समय के अनुपात को अपने अनुमानित फ़ंक्शन (एन^2) पर गणना करें:

for n = 5 to 10000 //n: problem size 
    long start = System.time() 
    executeAlgorithm(n) 
    long end = System.time() 
    long totalTime = end - start 

    double ratio = (double) time/(n * n) 
end 

। अनंत, इस अनुपात की ओर n चाल ... जैसा कि

• अभिमुख शून्य? फिर आपका अनुमान भी कम है। कुछ बड़ा के साथ दोहराएं (उदा। एन^3)
• अनंतता के लिए अलग हो जाता है? फिर आपका अनुमान भी उच्च है। कुछ छोटे (उदा। Nlogn)
• सकारात्मक स्थिरता के साथ दोहराएं? बिंगो!आपका अनुमान पैसे पर है (कम से कम के रूप में बड़े n मूल्यों के लिए सैद्धांतिक जटिलता का अनुमान लगाती है के रूप में आप की कोशिश की)

असल में है कि बड़ी हे संकेतन की परिभाषा का उपयोग करता है, कि f(x) = O(g(x)) <=> f(x) < c * g(x) - f(x) अपने एल्गोरिथ्म की वास्तविक लागत है, g(x) अनुमान लगाया गया है, और c एक स्थिर है। तो मूल रूप से आप प्रयोगात्मक रूप से f(x)/g(x) की सीमा को खोजने का प्रयास करते हैं; यदि आपका अनुमान वास्तविक जटिलता को हिट करता है, तो यह अनुपात निरंतर c का अनुमान लगाएगा।

Answer 6

जैसा कि अन्य ने उल्लेख किया है, सैद्धांतिक समय जटिलता आपके एल्गोरिदम द्वारा किए गए सीपीयू संचालन की संख्या का एक कार्य है। सामान्य प्रोसेसर समय में उस मॉड्यूल के लिए एक निरंतर अनुमान होना चाहिए। लेकिन असली रन टाइम जैसे कारणों की एक संख्या की वजह से भिन्न हो सकते हैं:

1. प्रोसेसर पाइपलाइन flushes
2. कैश याद करते हैं
3. कचरा संग्रहण
4. मशीन पर अन्य प्रक्रियाओं

जब तक आपका कोड व्यवस्थित रूप से इन चीजों में से कुछ को घटित कर रहा है, सांख्यिकीय नमूनों की पर्याप्त संख्या के साथ, आपको देखा गया रनटाइम के आधार पर आपके एल्गोरिदम की समय जटिलता का काफी अच्छा विचार होना चाहिए।