Table of Contents
एल्गोरिथ्म के समय और अंतरिक्ष जटिलता को समझना उनकी दक्षता का मूल्यांकन करने में मदद करता है। मर्ज सॉर्ट और क्विक सॉर्ट विभिन्न प्रदर्शन विशेषताओं के साथ दो लोकप्रिय सॉर्टिंग एल्गोरिदम हैं। यह लेख बताता है कि उनकी जटिलताओं की गणना कैसे की जाए।
मर्ज सॉर्ट जटिलता
मर्ज सॉर्ट प्रत्येक subarray एक तत्व शामिल होने तक, फिर से हलवे में सरणी को विभाजित करता है। विलय प्रक्रिया तब सॉर्ट ऑर्डर में इन subarrays को जोड़ती है।
विलय की समय जटिलता है O(n log n) ] सबसे अच्छा, औसत और खराब मामलों में क्योंकि यह लगातार सरणी को विभाजित करता है और इसे कुशलतापूर्वक विलय करता है।
अंतरिक्ष जटिलता है O(n) विलय प्रक्रिया के दौरान अस्थायी सरणी की आवश्यकता के कारण।
त्वरित वर्गीकरण
त्वरित प्रकार एक धुरी तत्व का चयन करता है और विभाजन सरणी को subarrays में करता है जो कि धुरी से कम या उससे अधिक है। इस प्रक्रिया को दोहराए जाने वाले तरीके से दोहराया जाता है।
औसत समय जटिलता है O(n log n), लेकिन सबसे खराब मामले में, जैसे कि जब सबसे छोटा या सबसे बड़ा तत्व हमेशा pivot के रूप में चुना जाता है, तो यह O(n^2)]] को degrade करता है।
त्वरित प्रकार के लिए अंतरिक्ष जटिलता आम तौर पर O(log n) ] है, जो पुनरावर्ती स्टैक स्पेस के कारण होता है, लेकिन यह कार्यान्वयन के आधार पर अधिक हो सकता है।
जटिलता का सारांश
- मर्ज सॉर्ट - टाइम: O(n log n) , स्पेस: O(n]]]]]
- त्वरित क्रमबद्ध - समय: Average O(n log n)], Worst O(n^2), स्पेस: ]O(log n)]]