यह देखने के लिए काउंटर को रखकर किया जा सकता है कि एल्गोरिदम कितने पुनरावृत्तियों से गुज़रता है, या समय अवधि को रिकॉर्ड करने की आवश्यकता होती है?एक परीक्षण समय जटिलता "प्रयोगात्मक" कैसे कर सकता है?
उत्तर
एल्गोरिथ्म जटिलता के रूप में परिभाषित किया गया है (जैसे :)
संचालन की संख्या एल्गोरिथ्म अपने इनपुट आकार के एक समारोह के रूप में करता है कुछ। एल्गोरिथ्म, - (10 तत्वों, 100 तत्वों आदि छँटाई कोशिश यानी प्रकार के लिए) और प्रत्येक आपरेशन (जैसे काम, वेतन वृद्धि, गणितीय प्रक्रिया आदि) गिनती
तो तुम विभिन्न इनपुट आकार के साथ अपने एल्गोरिथ्म प्रयास करने की आवश्यकता कर देता है।
यह आपको एक अच्छा "सैद्धांतिक" अनुमान देगा।
यदि आप दूसरी ओर वास्तविक जीवन संख्या चाहते हैं - profiling का उपयोग करें।
इसके अलावा, एल्गोरिदम जटिलता सभी परिचालनों की अवधि में परिभाषित नहीं की जाती है। उदाहरण के लिए यह मानना सामान्य है कि पूर्णांक अतिरिक्त ओ (1) है, जबकि बड़े पूर्णांक जोड़ों के लिए ओ (लॉग एन) है जहां एन पूर्णांक है। इसका मतलब यह है कि किसी दिए गए एल्गोरिदम के लिए एक एल्गोरिदम जटिलता नहीं है: यह भी निर्भर करता है कि आप किस परिचालन में रुचि रखते हैं (आमतौर पर सबसे महंगा), यही कारण है कि सॉर्टिंग एल्गोरिदम जटिलता आवश्यक तुलना की संख्या की अवधि में व्यक्त की जाती है। –
हां।
आप दोनों वास्तविक प्रदर्शन और पुनरावृत्तियों की संख्या को ट्रैक कर सकते हैं।
क्या मैं एएनटीएस प्रोफाइलर का उपयोग करने का सुझाव दे सकता हूं। जब आप अपने ऐप को "प्रयोगात्मक" डेटा के साथ चलाते हैं तो यह आपको इस तरह की जानकारी प्रदान करेगा।
वास्तव में आपके एल्गोरिदम द्वारा किए गए "संचालन" की संख्या को गिनने का सबसे अच्छा तरीका होगा। "ऑपरेशन" की परिभाषा भिन्न हो सकती है: क्विकॉर्ट जैसे एल्गोरिदम के लिए, यह दो संख्याओं की तुलना की संख्या हो सकती है।
आप किसी न किसी अनुमान के लिए आपके कार्यक्रम द्वारा उठाए गए समय को माप सकते हैं, लेकिन विभिन्न कारक वास्तविक मूल्य गणितीय जटिलता से भिन्न हो सकते हैं।
वर्तमान में स्वीकृत आपको कोई सैद्धांतिक अनुमान नहीं देगा, जब तक कि आप प्रयोगात्मक रूप से मापा गया समय फिट करने में सक्षम नहीं होते हैं जो उन्हें अनुमानित करता है। यह उत्तर आपको ऐसा करने के लिए एक मैन्युअल तकनीक देता है और उस अंतर को भरता है।
आप एल्गोरिदम के सैद्धांतिक जटिलता समारोह अनुमान लगाते हैं। आप तेजी से बड़ी समस्याओं के लिए वास्तविक जटिलता (परिचालन, समय, या जो भी आपको व्यावहारिक पाते हैं) का प्रयोगात्मक रूप से मापते हैं।
उदाहरण के लिए, मान लें कि एक एल्गोरिदम वर्ग है। समय को मापें (कहें), और समय के अनुपात को अपने अनुमानित फ़ंक्शन (एन^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
का अनुमान लगाएगा।
जैसा कि अन्य ने उल्लेख किया है, सैद्धांतिक समय जटिलता आपके एल्गोरिदम द्वारा किए गए सीपीयू संचालन की संख्या का एक कार्य है। सामान्य प्रोसेसर समय में उस मॉड्यूल के लिए एक निरंतर अनुमान होना चाहिए। लेकिन असली रन टाइम जैसे कारणों की एक संख्या की वजह से भिन्न हो सकते हैं:
- प्रोसेसर पाइपलाइन flushes
- कैश याद करते हैं
- कचरा संग्रहण
- मशीन पर अन्य प्रक्रियाओं
जब तक आपका कोड व्यवस्थित रूप से इन चीजों में से कुछ को घटित कर रहा है, सांख्यिकीय नमूनों की पर्याप्त संख्या के साथ, आपको देखा गया रनटाइम के आधार पर आपके एल्गोरिदम की समय जटिलता का काफी अच्छा विचार होना चाहिए।
- 1. समय जटिलता
- 2. समय जटिलता()
- 3. समय जटिलता
- 4. समय जटिलता()
- 5. समय जटिलता
- 6. एक पुनरावर्ती एल्गोरिदम की समय जटिलता
- 7. गैलप खोज समय जटिलता?
- 8. डेटाबेस क्वेरी समय जटिलता
- 9. random.sample की समय जटिलता
- 10. समय जटिलता अजगर
- 11. ट्रीमैप - खोज समय जटिलता
- 12. समय जटिलता को सत्यापित करने के लिए यूनिट परीक्षण
- 13. ट्रीसेट पुनरावृत्ति की समय जटिलता क्या है?
- 14. मैं समय-सीमित परीक्षण आवेदन कैसे कर सकता हूं?
- 15. प्राइम का एल्गोरिदम समय जटिलता
- 16. स्मृति आवंटन की समय जटिलता
- 17. एक समय-सीमित परीक्षण
- 18. मैट्रिक्स गुणा एल्गोरिदम समय जटिलता
- 19. सेट समय और गति जटिलता
- 20. यादृच्छिक संतुलित प्रयोगात्मक डिजाइन
- 21. प्राथमिकता कतार जटिलता समय हटाएं
- 22. हैश टेबल की समय जटिलता
- 23. पायथन सेट ऑपरेशंस की समय जटिलता?
- 24. MSTest: कैसे परीक्षण समय
- 25. एसवीएन शाखा प्रतिबद्ध - प्रयोगात्मक प्रतिबद्धता
- 26. जावा में सेट की समय जटिलता
- 27. एल्गोरिदम की कंप्यूटिंग समय जटिलता पर संसाधन
- 28. मैं कैसे परीक्षण कर सकता हूं: RSpec
- 29. मैं जीसी परीक्षण कैसे कर सकता हूं?
- 30. मैं एक विंडोज सेवा का परीक्षण कैसे कर सकता हूं?
आम तौर पर शोध पत्रों में आप सिद्धांत से जटिलता तर्क देखते हैं लेकिन सॉफ्टवेयर में सैद्धांतिक जटिलता की गिनती करने की कोशिश करने के बजाय वास्तविक रन टाइम - जटिलता के बारे में सोचने का बिंदु दक्षता में अंतर्दृष्टि प्राप्त करना है, और दक्षता का उपाय यह है कि कैसे तेजी से कार्यक्रम चलता है (या कभी-कभी अन्य संसाधनों जैसे मेमोरी का उपभोग करता है) –