सिंपलक्स एल्गोरिदम में घातीय सबसे खराब केस समय जटिलता कहा जाता है। फिर भी यह अक्सर अभ्यास में प्रयोग किया जाता है। आप किसी निश्चित समस्या के लिए औसत समय जटिलता कैसे निर्धारित कर सकते हैं (सरल के साथ हल किया जा रहा है)।सरल समय जटिलता (यानी अधिकतम प्रवाह) निर्धारित करने के लिए कैसे करें
उदाहरण के लिए, सरल प्रवाह एल्गोरिदम के साथ अधिकतम प्रवाह समस्या का औसत समय जटिलता क्या है। (विकी में अन्य सभी एल्गोरिदम के लिए समय जटिलता है)
आपके समय के लिए धन्यवाद।
औसत केस जटिलता का विश्लेषण करना मुश्किल है और यह आपके रैखिक कार्यक्रम के वितरण पर निर्भर करता है। मेरा मानना है कि यह कुछ आम वितरणों के तहत बहुपद समय के लिए काम किया गया था। मैं वर्तमान में कागज नहीं मिल सकता है।
संपादित:
Nocedal, जे और राइट, एस.जे. संख्यात्मक अनुकूलन: हाँ, यहाँ स्रोत हैं। न्यूयॉर्क: स्प्रिंगर-वेरलाग, 1 999।
फोर्सग्रेन, ए .; गिल, पी। ई .; और राइट, एम एच। "Nonlinear अनुकूलन के लिए आंतरिक तरीके।" सियाम रेव 44, 525-597, 2002.
मैंने इसे पहली पुस्तक में पढ़ा और जाहिर है कि यह एक अलग पेपर (फोर्सग्रेन) में साबित हुआ था। आप या तो विश्वविद्यालय पुस्तकालय में पा सकते हैं।
यदि यह अभी भी दिलचस्प है। सरलक्स की समय जटिलता ओ ((एन + एम) * एन) है।
एन - चर की संख्या।
मीटर - असमानता बाधाएं।
क्यों? क्योंकि के मामले में पुनरावृत्तियों की संख्या n + m से अधिक नहीं हो सकती है जो कि शीर्षकों की संख्या पर ऊपरी सीमा है।
लेकिन यह ऊपरी सीमा एन में घातीय है।
होमवर्क/परीक्षण प्रश्न की तरह लगता है। –
+1 यह वास्तव में एक गहरा सवाल है और मुझे यकीन नहीं है कि किसी ने पहले यह काम किया है या नहीं। मैं जवाब सुनने के लिए बहुत उत्सुक हूँ। – templatetypedef