एल्गोरिदम की सटीक जटिलता की गणना कैसे करें?

Question

एसिम्प्टोटिक नोटेशन का उपयोग किए बिना, एक एल्गोरिदम की समय जटिलता प्राप्त करने का एकमात्र तरीका गिनती कठिन कदम है? और कोड की प्रत्येक पंक्ति के चरणबद्ध गिनती के बिना हम किसी भी कार्यक्रम के बड़े-बड़े प्रतिनिधित्व पर पहुंच सकते हैं?

विवरण: कई संख्यात्मक विश्लेषण एल्गोरिदम की जटिलता को जानने का प्रयास करने के लिए यह तय करने के लिए कि कौन सी विशेष समस्या को हल करने के लिए सबसे उपयुक्त होगा। ईजी। - eqns को हल करने के लिए रेगुला-फाल्सी या न्यूटन-रेस्पॉन विधि के बीच, इरादा प्रत्येक विधि की सटीक जटिलता का मूल्यांकन करना है और फिर निर्णय लेना है ('एन' का मूल्य डालना या जो भी तर्क हैं) कौन सी विधि कम जटिल है।

Answer 1

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

लेकिन, यदि आप स्वचालित रूप से चरणों गिनती करने के लिए करना चाहता था, वहाँ भी ऐसा करने के लिए तरीके हैं। आप कोड की प्रत्येक पंक्ति में काउंटर वृद्धि कमांड (जैसे सी में "ब्लूफ ++;") जोड़ सकते हैं, और फिर अंत में मान प्रदर्शित कर सकते हैं।

तुम भी अधिक परिष्कृत समय जटिलता अभिव्यक्ति, च (एन) * के बारे में पता होना चाहिए (1 + ओ (1)), वह भी विश्लेषणात्मक गणना के लिए उपयोगी है। उदाहरण के लिए n^2 + 2 * n + 7 n^2 * (1 + o (1)) को सरल बनाता है। यदि निरंतर कारक आपको सामान्य एसिम्प्टोटिक नोटेशन ओ (एफ (एन)) के बारे में परेशान करता है, तो यह परिष्करण इसका ट्रैक रखने का एक तरीका है और अभी भी नगण्य शर्तों को फेंक देता है।

Answer 2

'आसान तरीका' इसे अनुकरण करना है। अपने एल्गोरिदम को एन के बहुत सारे मानों और विभिन्न डेटा के साथ आज़माएं, परिणामों को साजिश करें, फिर ग्राफ पर एक समीकरण के वक्र से मेल खाते हैं।

आपका परिणाम सख्ती से सही नहीं हो सकता है और वे केवल अच्छा परीक्षण डेटा उत्पन्न करने की क्षमता के रूप में लेकिन ज्यादातर मामलों में इस काम करेंगे के लिए के रूप में मान्य हो।

Answer 3

जैसे - eqns को हल करने के लिए रेगुला-फाल्सी या न्यूटन-रेस्पॉन विधि के बीच, इरादा प्रत्येक विधि की सटीक जटिलता का मूल्यांकन करना है और फिर निर्णय लेना है ('एन' का मूल्य डालना या जो भी तर्क हैं) कौन सी विधि कम जटिल है।

मुझे नहीं लगता कि सामान्य रूप से nonlinear solvers के लिए इस प्रश्न का उत्तर देना संभव है। आप प्रति पुनरावृत्ति की गणना की सटीक संख्या कर सकते हैं, लेकिन आप सामान्य रूप से कभी नहीं जान पाएंगे कि प्रत्येक सॉल्वर को अभिसरण करने के लिए कितना पुनरावृत्ति होगा। न्यूटन के लिए जैकोबियन की आवश्यकता जैसी अन्य जटिलताओं हैं जो जटिलता की गणना को और भी कठिन बना सकती हैं।

सारांश में, सबसे कुशल nonlinear solver हमेशा समस्या आप को सुलझाने रहे हैं पर निर्भर है। यदि आप जिन समस्याओं को हल कर रहे हैं, वे बहुत सीमित हैं, विभिन्न हलकों के साथ प्रयोगों का एक गुच्छा कर रहे हैं और पुनरावृत्तियों और सीपीयू समय की संख्या को मापने से आपको अधिक उपयोगी जानकारी मिल जाएगी।