एल्गोरिदम का विश्लेषण (जटिलता)

Question

एल्गोरिदम का विश्लेषण कैसे किया जाता है? क्या Quicksort में O(n^2) खराब-केस प्रदर्शन होता है जबकि विलय सॉर्ट में O(n log(n)) सबसे खराब-केस प्रदर्शन होता है?

Answer 1

यह पूरे सेमेस्टर के लिए एक विषय है। आखिरकार हम संचालन की संख्या पर ऊपरी बाउंड के बारे में बात कर रहे हैं जो इनपुट के आकार के कार्य के रूप में एल्गोरिदम खत्म होने से पहले पूरा किया जाना चाहिए। हम सहकारी (यानी 10 एन बनाम 4 एन^2) शामिल नहीं करते हैं क्योंकि एन पर्याप्त रूप से पर्याप्त है, इससे कोई फर्क नहीं पड़ता।

साबित करने के लिए कि एल्गोरिदम का बड़ा-ओह कितना मुश्किल हो सकता है। इसे औपचारिक प्रमाण की आवश्यकता है और कई तकनीकें हैं। अक्सर एक अच्छा adhoc तरीका यह है कि एल्गोरिदम बनाता है डेटा पर कितने पास गुजरता है। उदाहरण के लिए, यदि आपके एल्गोरिदम ने लूप के लिए घोंसला लिया है, तो प्रत्येक एन आइटम के लिए आपको एन बार संचालित करना होगा। वह आमतौर पर ओ (एन^2) होगा।

सॉर्ट विलय करने के लिए, आप डेटा को आधे से अधिक में विभाजित करते हैं। यह लॉग 2 (एन) लेता है। और प्रत्येक विभाजन के लिए आप डेटा पर एक पास करते हैं, जो एन लॉग (एन) देता है।

त्वरित क्रम थोड़ा सा चालक है क्योंकि औसत मामले में यह भी एन लॉग (एन) है। आपको कल्पना करना होगा कि क्या होता है यदि आपका विभाजन डेटा को विभाजित करता है जैसे हर बार जब आप विभाजन के एक तरफ केवल एक तत्व प्राप्त करते हैं। फिर आपको लॉग (एन) के बजाय डेटा एन बार विभाजित करने की आवश्यकता होगी जो इसे एन^2 बनाता है। क्विकॉर्ट का लाभ यह है कि यह जगह में किया जा सकता है, और हम आम तौर पर एन लॉग (एन) प्रदर्शन के करीब आते हैं।

Answer 2

quicksort और merge sort दोनों सरणी को दो में विभाजित करें, प्रत्येक भाग को क्रमशः क्रमबद्ध करें, फिर परिणाम को गठबंधन करें। Quicksort एक "पिवट" तत्व चुनकर विभाजित करता है और सरणी को छोटे या बड़े में पिवोट में विभाजित करता है। क्रमबद्ध रूप से विभाजित विभाजन को मर्ज करें और फिर परिणामों को रैखिक समय में विलीन करें। दोनों मामलों में एक ही चरण ओ (एन) है, और यदि सरणी आकार हर बार आधा होता है तो यह एक लॉगरिदमिक चरणों की संख्या देगा। तो हम ओ (एन लॉग (एन)) की उम्मीद करेंगे।

हालांकि क्विक्सॉर्ट का सबसे खराब मामला है जहां विभाजन हमेशा असमान होता है, इसलिए आपको एन के लॉगरिदमिक के अनुपात में कई कदम नहीं मिलते हैं, लेकिन एन के आनुपातिक कई कदम हैं। सॉर्ट स्प्लिट को दो हिस्सों में विभाजित करें (या जितना संभव हो सके बंद करें) इसलिए इसमें यह समस्या नहीं है।

Answer 3

• त्वरित प्रकार धुरी चयन के आधार पर कई भिन्न रूप
• मान लेते हैं कि हम हमेशा एक धुरी

के रूप में सरणी में 1 आइटम का चयन करते हैं इनपुट सरणी सॉर्ट किया जाता है, तो त्वरित प्रकार केवल एक हो जाएगा है चयन प्रकार की तरह! क्योंकि आप वास्तव में सरणी को विभाजित नहीं कर रहे हैं .. आप केवल प्रत्येक चक्र

पर पहले आइटम चुन रहे हैं दूसरी ओर मर्ज सॉर्ट हमेशा इसकी सामग्री के बावजूद इनपुट सरणी को उसी तरीके से विभाजित करेगा!

यह भी ध्यान दें: विभाजित होने में सबसे अच्छा प्रदर्शन और डिवीजन की लंबाई के दौरान जीतें - लगभग-बराबर!

Answer 4

1. यह एल्गोरिदम पाठ्यक्रम सामग्री का प्रारंभिक विश्लेषण है।

2. एक ऑपरेशन परिभाषित किया गया है (यानी गुणा) और विश्लेषण अंतरिक्ष या समय के संदर्भ में किया जाता है।

3. यह ऑपरेशन अंतरिक्ष या समय के संदर्भ में गिना जाता है।आम तौर पर विश्लेषण इनपुट आकार पर आश्रित चर होने के रूप में किया जाता है।

उदाहरण स्यूडोकोड:

foreach $elem in @list 

    op(); 

endfor 

वहाँ n संचालन, प्रदर्शन किया जहां n@list के आकार है किया जाएगा। अगर आप मुझ पर विश्वास नहीं करते हैं तो इसे स्वयं गिनें।

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